CQUPT OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#16349 #1064. ComistryMo和乡下小镇 Runtime Error 95 1085 ms 9284 K C++ 17 / 1.6 K 192023212359 2024-03-16 15:46:05
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 3e5 + 5;

//
#define lowbit(x) ((x) & -(x))

int tree[N + 1000] = { 0 };
int n, m;
void add(int x, int d) {
    while (x <= N) {
        tree[x] += d;
        x += lowbit(x);
    }
}

int ask(int x) {
    int ans = 0;
    while (x > 0) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
//
struct node {
    int g, f, id;
} a[200005], b[200005];

bool cmpb(node x, node y) {
    if (x.g == y.g)
        return x.f < y.f;
    return x.g < y.g;
}

bool cmpa(node x, node y) {
    if (x.f == y.f)
        return x.g < y.g;
    return x.f < y.f;
}

int ans[N];

// lisanhua
vector<int> alls;

int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return r + 1;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &a[i].g, &a[i].f);
        alls.push_back(a[i].g), alls.push_back(a[i].f);
        a[i].id = i;
    }

    scanf("%lld", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld", &b[i].g, &b[i].f);
        alls.push_back(b[i].g), alls.push_back(b[i].f);
        b[i].id = i;
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    sort(a + 1, a + 1 + n, cmpa);
    sort(b + 1, b + 1 + m, cmpb);

    int j = 1;
    for (int i = 1; i <= m; i++) {
        while (j <= n && a[j].f <= b[i].g) {
            add(find(a[j].g), 1);
            //			printf("Add %lld\n", a[j].id);
            j++;
        }
        ans[b[i].id] = ask(find(b[i].f));
        //		printf("ASK %lld\n", b[i].id);
    }
    for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
}
子任务 #1
Runtime Error
得分：95
测试点 #1
Accepted
得分：100
用时：14 ms
内存：1356 KiB

输入文件（1.in） 

6526
881153780 329890560
75030547 52936344
785521614 46028774
363592456 349054921
367463908 15986035
<276605 bytes omitted>

答案文件（1.out） 

856
2181
5067
2914
4089
146
2793
3486
1199
1419
787
793
2292
3316
4973
6047
513
3802
1837
3046
3080

<34358 bytes omitted>

用户输出 

856
2181
5067
2914
4089
146
2793
3486
1199
1419
787
793
2292
3316
4973
6047
513
3802
1837
3046
3080
3642
829
5902
3142
452
1371

<34330 bytes omitted>

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：16 ms
内存：1472 KiB

输入文件（2.in） 

9999
636953749 492928929
535721810 16618411
890471883 774443702
874013197 848713588
668432865 596006
<338564 bytes omitted>

答案文件（2.out） 

546
638
7935
2678
2247
1521
983
530
790
5433
84
75
2521
813
139
1085
3844
1201
5345
456
2952
984
395
<33526 bytes omitted>

用户输出 

546
638
7935
2678
2247
1521
983
530
790
5433
84
75
2521
813
139
1085
3844
1201
5345
456
2952
984
3955
7604
631
745
223
1593
7298
<33498 bytes omitted>

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：11 ms
内存：1184 KiB

输入文件（3.in） 

9245
708356159 667253469
585853496 472896001
887239462 696011514
832983419 798997599
825023098 44831
<203240 bytes omitted>

答案文件（3.out） 

75
1340
5292
5302
6049
1570
807
1343
1672
561
2457
480
3922
5870
354
6905
2612
7475
1912
662
3510
60
<4770 bytes omitted>

用户输出 

75
1340
5292
5302
6049
1570
807
1343
1672
561
2457
480
3922
5870
354
6905
2612
7475
1912
662
3510
6079
12
5161
7944
2473
120
459
<4742 bytes omitted>

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：16 ms
内存：1464 KiB

输入文件（4.in） 

9309
373957407 76657044
472116554 196652553
386812077 111475551
752014122 610169068
212722072 208290
<302419 bytes omitted>

答案文件（4.out） 

2611
8437
5237
5112
3430
2782
2259
5089
763
4436
4547
2354
6971
2403
4277
1713
133
1417
5908
1818
19
<28142 bytes omitted>

用户输出 

2611
8437
5237
5112
3430
2782
2259
5089
763
4436
4547
2354
6971
2403
4277
1713
133
1417
5908
1818
1959
1163
7376
835
3723
3652
2
<28114 bytes omitted>

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：10 ms
内存：1136 KiB

输入文件（5.in） 

4900
133761260 92292691
601254146 238198382
926183276 783953392
649510580 648147816
972776460 114794
<183093 bytes omitted>

答案文件（5.out） 

1714
4659
544
4615
1220
3414
105
892
1413
1486
1497
2152
367
11
764
212
2063
2000
22
36
1746
2153
33
<19619 bytes omitted>

用户输出 

1714
4659
544
4615
1220
3414
105
892
1413
1486
1497
2152
367
11
764
212
2063
2000
22
36
1746
2153
33
1630
3073
423
831
216
1425

<19591 bytes omitted>

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：11 ms
内存：1080 KiB

输入文件（6.in） 

6732
312695100 295201367
733141488 568661170
696803709 68675076
464036508 227317672
839328471 723398
<200961 bytes omitted>

答案文件（6.out） 

938
499
167
2340
5237
945
2696
93
2354
392
578
3297
5232
2428
1079
1006
1423
3109
2092
3797
78
1789

<15830 bytes omitted>

用户输出 

938
499
167
2340
5237
945
2696
93
2354
392
578
3297
5232
2428
1079
1006
1423
3109
2092
3797
78
1789
5178
4901
4885
640
3978
1133
<15802 bytes omitted>

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：9 ms
内存：956 KiB

输入文件（7.in） 

5285
838372251 722597165
932558356 157344004
950595541 103357857
494057362 334372318
377870614 12913
<152660 bytes omitted>

答案文件（7.out） 

2915
485
3451
2665
847
2841
672
2024
4674
3618
1082
3920
881
3456
19
1275
1155
1614
2161
3564
736
28
<11043 bytes omitted>

用户输出 

2915
485
3451
2665
847
2841
672
2024
4674
3618
1082
3920
881
3456
19
1275
1155
1614
2161
3564
736
2877
4766
4
224
3
1012
2286
70
<11015 bytes omitted>

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：8 ms
内存：964 KiB

输入文件（8.in） 

4697
725606638 700644658
912161434 684852059
581859945 462743496
906746170 444174276
719940676 62637
<127968 bytes omitted>

答案文件（8.out） 

583
2873
2099
1870
931
4166
2923
629
72
2342
497
2689
576
2093
2218
970
246
2978
4250
995
2861
517
1
<7949 bytes omitted>

用户输出 

583
2873
2099
1870
931
4166
2923
629
72
2342
497
2689
576
2093
2218
970
246
2978
4250
995
2861
517
1150
796
2648
2336
121
1583
4
<7921 bytes omitted>

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：10 ms
内存：980 KiB

输入文件（9.in） 

3150
733307502 314607758
677974045 42621091
956587489 831001268
368140357 28054197
946944619 4841039
<126890 bytes omitted>

答案文件（9.out） 

536
237
432
481
174
1239
755
329
711
142
1337
1468
320
1804
2557
1303
177
1665
1284
485
1507
594
111
<14028 bytes omitted>

用户输出 

536
237
432
481
174
1239
755
329
711
142
1337
1468
320
1804
2557
1303
177
1665
1284
485
1507
594
1114
2371
666
3
110
42
37
897
9
<14000 bytes omitted>

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：8 ms
内存：948 KiB

输入文件（10.in） 

1328
757635041 598207989
105809559 105084516
686967582 32813843
465281835 140997315
482242307 102366
<112105 bytes omitted>

答案文件（10.out） 

859
674
350
184
268
18
555
307
1192
104
179
156
21
513
1247
224
345
558
291
11
34
592
205
103
473
35
<16694 bytes omitted>

用户输出 

859
674
350
184
268
18
555
307
1192
104
179
156
21
513
1247
224
345
558
291
11
34
592
205
103
473
350
542
848
1126
482
278
1001

<16666 bytes omitted>

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：112 ms
内存：8144 KiB

输入文件（11.in） 

56872
228728202 125054225
963840371 961815929
393952355 356403926
747793424 5257067
858551290 311404
<2566974 bytes omitted>

答案文件（11.out） 

13936
15377
3749
2384
22861
40573
19263
22291
4903
33052
2312
3732
27526
7225
24818
23040
8979
829
2
<406649 bytes omitted>

用户输出 

13936
15377
3749
2384
22861
40573
19263
22291
4903
33052
2312
3732
27526
7225
24818
23040
8979
829
2901
32548
3022
2175
1920
119
<406621 bytes omitted>

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：53 ms
内存：4264 KiB

输入文件（12.in） 

22589
689839269 489035524
887004244 350091703
767436589 660747891
715680393 197764844
660236265 1162
<1221061 bytes omitted>

答案文件（12.out） 

15785
13147
4645
2274
11741
7207
15994
2690
17362
11667
4945
18770
4580
9208
11922
2925
5577
4521
23
<202804 bytes omitted>

用户输出 

15785
13147
4645
2274
11741
7207
15994
2690
17362
11667
4945
18770
4580
9208
11922
2925
5577
4521
236
4452
2943
17907
5620
2000

<202776 bytes omitted>

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：62 ms
内存：4804 KiB

输入文件（13.in） 

25769
777719342 771952978
997338574 612696897
898337523 106085338
853115840 52447671
941698650 15107
<1404177 bytes omitted>

答案文件（13.out） 

3519
20712
6609
8890
10873
9636
22728
3122
500
19538
20350
2308
5556
5111
5731
4413
6741
3773
4092
9
<237341 bytes omitted>

用户输出 

3519
20712
6609
8890
10873
9636
22728
3122
500
19538
20350
2308
5556
5111
5731
4413
6741
3773
4092
9384
1113
9547
2749
79
2652
4
<237313 bytes omitted>

系统信息 

Exited with return code 0
测试点 #14
Runtime Error
得分：0
用时：105 ms
内存：7716 KiB

输入文件（14.in） 

82795
160594097 115816785
948193111 833242923
678628563 450115589
902829526 243377151
269406795 6898
<3363285 bytes omitted>

答案文件（14.out） 

12972
515
18047
756
21219
20375
22294
54733
11684
3233
23853
2318
31665
61300
2069
20266
19704
25169
<495745 bytes omitted>

系统信息 

Killed: Segmentation fault
测试点 #15
Accepted
得分：100
用时：86 ms
内存：6424 KiB

输入文件（15.in） 

91192
694618838 349973023
984515456 162172030
648075010 591987008
532149977 168540224
581025228 5629
<2073293 bytes omitted>

答案文件（15.out） 

10921
39875
15854
32119
24897
19786
20044
49659
29071
6355
74406
39014
79135
53016
42676
27851
9259

<77844 bytes omitted>

用户输出 

10921
39875
15854
32119
24897
19786
20044
49659
29071
6355
74406
39014
79135
53016
42676
27851
9259
81033
2155
23841
38716
73035
<77816 bytes omitted>

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：129 ms
内存：9284 KiB

输入文件（16.in） 

71389
648682094 130952543
633676522 262826503
931738407 385693099
175074584 153412826
740045299 7360
<2922847 bytes omitted>

答案文件（16.out） 

47274
14834
21979
25632
9031
26091
22479
9614
1950
60282
30899
7749
49450
30309
324
25893
31862
3983
<430854 bytes omitted>

用户输出 

47274
14834
21979
25632
9031
26091
22479
9614
1950
60282
30899
7749
49450
30309
324
25893
31862
39838
16811
34257
24652
28788
45
<430826 bytes omitted>

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：78 ms
内存：5924 KiB

输入文件（17.in） 

59001
557696458 407197515
676949203 495534851
878700238 85938517
700004384 181490261
424381254 15546
<1835418 bytes omitted>

答案文件（17.out） 

10986
25924
50181
16119
32145
28731
8644
2772
15076
30511
41703
8072
11323
35694
17231
9044
2266
375
<188696 bytes omitted>

用户输出 

10986
25924
50181
16119
32145
28731
8644
2772
15076
30511
41703
8072
11323
35694
17231
9044
2266
37539
1210
28848
42221
33875
22
<188668 bytes omitted>

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：129 ms
内存：9156 KiB

输入文件（18.in） 

71986
273379872 29801096
96306372 34962588
224468008 76821315
744767204 114848691
480734341 14140440
<2919763 bytes omitted>

答案文件（18.out） 

40072
7131
17951
36920
4485
5188
30471
7365
23177
43775
20406
22281
11408
50779
26933
57586
15549
49
<426757 bytes omitted>

用户输出 

40072
7131
17951
36920
4485
5188
30471
7365
23177
43775
20406
22281
11408
50779
26933
57586
15549
49040
16584
45849
25279
20072

<426729 bytes omitted>

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：88 ms
内存：6400 KiB

输入文件（19.in） 

71688
944465125 527562360
908728637 562695197
246379284 212055045
249306074 8381552
773928690 512928
<2027208 bytes omitted>

答案文件（19.out） 

450
1770
42936
4663
55
27614
24686
65332
62561
14921
3448
2756
19351
3719
36438
32740
7795
19467
181
<173711 bytes omitted>

用户输出 

450
1770
42936
4663
55
27614
24686
65332
62561
14921
3448
2756
19351
3719
36438
32740
7795
19467
18103
62610
2643
2606
33184
671
<173683 bytes omitted>

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：130 ms
内存：9172 KiB

输入文件（20.in） 

97692
956085543 346233370
722791122 25259193
315533463 77876288
196459767 76673715
792473962 1148883
<2953680 bytes omitted>

答案文件（20.out） 

54493
4190
28110
37202
22992
85058
74026
54044
25263
49535
651
65194
22337
68448
36183
5158
8733
114
<295379 bytes omitted>

用户输出 

54493
4190
28110
37202
22992
85058
74026
54044
25263
49535
651
65194
22337
68448
36183
5158
8733
1144
68787
588
31329
4279
32124
<295351 bytes omitted>

系统信息 

Exited with return code 0
CQUPT OJ Powered by SYZOJ.