QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746796#62. ExaminationShumomo2 26ms10088kbC++141.8kb2024-11-14 15:34:432024-11-14 15:34:44

Judging History

你现在查看的是最新测评结果

  • [2024-11-14 15:34:44]
  • 评测
  • 测评结果:2
  • 用时:26ms
  • 内存:10088kb
  • [2024-11-14 15:34:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
struct node{
    int a,b,c,d;
    bool operator <(const node &aa)const{
        return a<aa.a||(a==aa.a&&d>aa.d);
    }
}x[200009],y[200009];
int n,q,f[200009],ans[200009],v[200009];
void solve(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    solve(l,mid);
    solve(mid+1,r);
    int nw=r,ll=mid,rr=r;
    while(ll>=l&&rr>mid){
        if(x[ll].b>x[rr].b){
            if(x[ll].d>0){
                for(int i=x[ll].c;i;i-=(i&(-i)))ans[x[ll].d]+=v[i];
            }
            y[nw--]=x[ll--];
        }
        else {
            if(x[rr].d<0)for(int i=x[rr].c;i<=n+q;i+=(i&(-i)))v[i]++;
            y[nw--]=x[rr--];
        }
    }
    while(ll>=l){
        if(x[ll].d>0){
            for(int i=x[ll].c;i;i-=(i&(-i)))ans[x[ll].d]+=v[i];
        }
        y[nw--]=x[ll--];
    }
    while(rr>mid){
        if(x[rr].d<0)for(int i=x[rr].c;i<=n+q;i+=(i&(-i)))v[i]++;
        y[nw--]=x[rr--];
    }
    for(int i=mid+1;i<=r;i++){
        if(x[i].d<0)for(int j=x[i].c;j<=n+q;j+=(j&(-j)))v[j]--;
    }
    for(int i=1;i<=n+q;i++)assert(!v[i]);
    for(int i=l;i<=r;i++){
        x[i]=y[i];
    }
    return;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x[i].a,&x[i].b);
        x[i].c=x[i].a+x[i].b;
        x[i].d=-i;
        f[i]=x[i].c;
    }
    for(int i=n+1;i<=n+q;i++){
        scanf("%d%d%d",&x[i].a,&x[i].b,&x[i].c);
        x[i].d=i-n;
        f[i]=x[i].c;
    }
    sort(f+1,f+n+q+1);
    for(int i=1;i<=n+q;i++){
        x[i].c=lower_bound(f+1,f+n+q+1,x[i].c)-f;
        x[i].c=n+q+1-x[i].c;
    }
    sort(x+1,x+n+q+1);
    solve(1,n+q);
    for(int i=1;i<=q;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 1ms
memory: 8004kb

input:

10 10
28 2
78 81
39 79
61 31
36 99
90 5
20 55
91 4
48 19
80 7
52 43 78
64 65 171
34 68 124
37 80 161
53 19 123
49 58 109
95 46 30
45 48 60
47 13 54
64 30 144

output:

1
0
2
0
1
1
0
1
3
1

result:

ok 10 lines

Test #2:

score: 2
Accepted
time: 1ms
memory: 10088kb

input:

10 10
6 67
36 99
13 45
100 87
60 72
55 41
62 92
55 39
90 22
0 99
34 89 79
17 17 23
60 26 171
29 88 190
32 71 98
20 29 192
50 7 34
14 21 139
54 35 103
86 91 1

output:

2
7
1
0
4
0
6
2
3
0

result:

ok 10 lines

Test #3:

score: 2
Accepted
time: 1ms
memory: 7876kb

input:

10 10
67 72
94 99
34 22
1 71
68 18
90 94
29 44
98 61
46 9
94 76
73 36 11
30 26 75
5 85 112
38 35 111
39 72 143
6 64 130
31 24 134
82 86 188
80 20 151
91 32 62

output:

4
5
2
5
3
4
5
1
4
3

result:

ok 10 lines

Test #4:

score: 2
Accepted
time: 1ms
memory: 7940kb

input:

10 10
667489048 282547819
694873877 525794923
605957229 147658688
928289876 455560133
465507205 531350815
397977066 913356070
351069660 834164613
611261253 238522918
683770744 737447844
351350094 473152918
514777487 599392520 569824365
137189600 455145855 1628925058
608994260 433029864 1934471803
80...

output:

1
0
0
1
2
0
10
0
1
0

result:

ok 10 lines

Test #5:

score: 2
Accepted
time: 1ms
memory: 9908kb

input:

10 10
263981199 52332634
326795173 857652684
184061837 846545137
39542400 348620078
96871071 314776708
19327149 702608210
486997547 362493836
734600837 228406106
676322287 184313447
205910594 985010975
928597138 172342418 665625750
340192959 922085230 1825805421
805685495 219541540 475070350
4658221...

output:

0
0
0
3
0
0
3
0
0
0

result:

ok 10 lines

Test #6:

score: 2
Accepted
time: 0ms
memory: 8004kb

input:

10 10
938568749 622216614
473949650 794427283
821003445 932759572
521639872 980300286
221194869 486910867
809253866 513217132
566374168 282501808
288139033 402357178
916473963 145958981
592255402 968995324
113069862 909714805 1855286879
572813519 935368048 360790753
835912982 28401519 1522137034
943...

output:

0
1
1
0
2
0
7
0
2
9

result:

ok 10 lines

Test #7:

score: 2
Accepted
time: 26ms
memory: 7940kb

input:

3000 3000
40944019 692692877
645016109 145199524
568250169 363353983
626494606 558783087
161612818 101360006
34139264 867093007
708172540 84650861
45799594 79255002
364942843 522551858
327755779 907461393
429041284 748255933
912770818 886733119
19971581 580290777
717292638 606814849
840433536 332990...

output:

1602
171
930
467
30
1316
125
475
883
1105
135
427
478
89
840
1466
3
0
591
34
368
4
936
590
246
270
1168
18
79
9
303
533
19
491
163
287
1350
445
23
151
2006
184
1233
11
175
1348
515
229
717
889
60
37
4
273
324
81
4
471
1275
11
207
444
1214
232
85
686
182
709
513
207
1451
418
2041
729
3
871
466
51
198...

result:

ok 3000 lines

Test #8:

score: 2
Accepted
time: 22ms
memory: 8004kb

input:

3000 3000
907627167 686752093
462625412 852663910
500152795 14286796
910681862 200991087
109311919 35030354
156913954 564324169
181028206 930471944
686123971 163012566
732920495 314853990
910305661 51938497
868182462 323159996
777537241 919935911
714475342 334517770
927209935 435695974
747799830 888...

output:

70
62
456
163
1557
359
169
428
194
70
364
593
296
99
4
166
435
632
1
1315
21
137
72
375
111
674
491
1398
96
339
280
1
211
94
890
0
757
106
428
478
637
133
357
1009
422
706
224
111
231
677
21
990
1361
113
682
393
6
186
295
288
28
1586
82
186
21
92
64
416
127
453
174
500
8
374
257
10
195
441
213
2292
...

result:

ok 3000 lines

Test #9:

score: 2
Accepted
time: 22ms
memory: 10076kb

input:

3000 3000
334978095 565095638
78003245 739839219
211920625 294829
835598279 911193731
640309078 196393030
930111636 843404908
272429756 299106119
421405869 635269635
422157528 163791651
220891615 341620330
768573478 656606438
898559946 184092507
551655307 968524071
495019662 642996661
48050546 23559...

output:

305
17
1801
760
1981
737
261
136
282
495
8
58
117
102
1053
922
6
872
1305
1011
443
286
458
14
22
72
150
1341
537
403
4
885
626
1328
39
442
324
0
1456
210
35
539
1153
278
162
961
55
4
790
90
3
957
155
891
396
2412
63
0
1018
2211
176
432
152
33
440
230
238
139
314
69
311
3
936
136
730
1366
106
440
823...

result:

ok 3000 lines

Test #10:

score: 2
Accepted
time: 25ms
memory: 7888kb

input:

3000 3000
670721945 0
918363246 4
530498664 8
151236440 1
551302032 5
744761966 3
677885226 8
425828663 4
806962929 7
86226431 3
553505514 6
229344072 1
495287254 4
742717671 8
107255479 2
872256841 10
891288366 1
344265685 9
837502103 4
146091952 6
611328716 3
592876764 10
641850002 6
898856374 8
4...

output:

381
125
529
344
665
51
17
830
103
605
395
668
1507
1322
189
387
590
828
510
84
960
14
491
377
520
770
101
369
839
31
217
830
524
1477
205
87
12
996
235
521
2051
1117
238
178
1127
47
222
281
11
363
158
34
302
587
1408
287
1768
67
680
327
400
118
1591
804
84
162
1278
0
258
173
655
101
502
1012
565
269...

result:

ok 3000 lines

Test #11:

score: 2
Accepted
time: 22ms
memory: 7984kb

input:

3000 3000
8 375396159
8 368119562
1 575071003
0 713872346
8 587408547
7 78445830
3 900615065
0 97512137
4 875603716
3 187655071
3 321929391
4 341544316
5 427645484
5 264570850
8 560506150
8 208439714
3 264016831
2 461763351
1 831864441
5 487169227
3 762640963
4 222377711
10 632245214
7 14464390
9 40...

output:

1504
128
221
73
789
375
3
1103
2391
155
307
592
149
25
106
112
393
461
842
403
752
119
51
896
392
631
71
93
1182
753
334
2273
624
530
488
1465
13
5
1289
3
162
1744
511
164
612
435
801
1720
1017
855
1291
952
1096
593
299
31
158
219
420
37
66
991
193
2231
117
1357
388
363
18
1443
1054
486
107
72
32
39...

result:

ok 3000 lines

Test #12:

score: 2
Accepted
time: 24ms
memory: 7968kb

input:

3000 3000
8 9
5 2
9 2
6 5
3 3
9 10
6 10
5 1
4 9
4 3
0 9
4 3
0 4
10 3
2 2
8 7
10 5
4 0
9 9
7 9
2 2
10 3
1 2
10 5
7 2
7 8
0 10
4 3
2 10
10 1
5 9
3 5
5 4
7 1
4 4
7 6
7 2
6 4
9 7
2 9
3 2
0 10
3 6
6 7
8 0
5 10
0 2
6 3
0 6
2 3
4 2
5 3
10 6
9 0
5 5
3 10
5 0
1 7
9 9
0 7
7 3
8 9
2 3
3 1
8 10
4 7
10 10
10 3
0...

output:

1325
19
361
137
168
434
170
57
896
360
168
950
324
2158
338
510
116
215
1550
1163
132
896
2054
94
137
359
259
297
1973
1061
199
1475
510
365
343
225
804
235
235
279
19
281
365
236
894
1554
1619
116
1163
2443
1964
510
484
784
294
91
660
132
739
983
1087
195
1319
273
583
33
1932
876
146
365
371
203
59...

result:

ok 3000 lines

Test #13:

score: 2
Accepted
time: 26ms
memory: 8012kb

input:

3000 3000
877137497 911480796
105327974 808804262
727937300 637853442
718031794 765195805
838206925 484239980
607467843 605792963
38697321 332194606
273988991 323047106
798562928 435509930
372308224 443534703
707117309 487932296
211775547 761591409
77454450 882287786
277784786 263090911
819288578 17...

output:

1524
1296
1606
226
1445
158
382
435
13
182
1983
223
81
1832
469
1188
375
353
617
882
244
939
819
612
448
355
458
296
1024
301
855
732
1256
553
1143
755
978
1995
1263
1652
2018
239
38
1472
916
1172
662
1021
366
1480
136
716
1246
420
1549
24
257
831
143
164
466
1551
1476
499
1488
937
511
85
652
134
85...

result:

ok 3000 lines

Test #14:

score: 2
Accepted
time: 25ms
memory: 7964kb

input:

3000 3000
10427381 302072811
305423535 159511618
389241521 972714841
87239050 654013994
553105278 55046924
721109311 612092521
522048131 811507269
616929981 759331556
694803970 82587802
55757168 4610834
227644683 145826047
767743895 527337462
664853723 570569400
225987816 848995384
922146032 1350592...

output:

149
135
169
182
111
161
1515
1355
1736
2239
249
682
1721
1992
2006
1036
652
1810
577
810
471
1122
513
107
64
1907
1482
1707
531
972
679
197
34
382
7
107
623
573
132
767
61
106
60
1957
69
34
103
456
4
896
1516
1571
570
1885
573
1237
1652
433
1428
1
133
31
761
31
2282
591
1418
2078
102
21
212
1090
687...

result:

ok 3000 lines

Test #15:

score: 2
Accepted
time: 25ms
memory: 8060kb

input:

3000 3000
81888039 43067130
107207950 11840118
12213117 1564707
591852272 88838686
961663048 516561908
168803247 844631606
873195252 827482721
743609372 619362988
538294586 82184626
144127316 243409881
211682136 271003480
663591068 168473714
654369343 16498796
591919034 700712174
385773732 618206738...

output:

128
125
1701
799
67
1725
1166
370
80
481
533
606
82
8
2273
272
2646
637
955
661
484
2418
63
47
269
162
1864
364
873
135
947
401
126
1380
56
54
2756
279
352
327
633
1453
114
319
1142
219
5
1100
495
88
13
1948
37
773
823
284
1012
612
195
248
1585
1517
37
159
1940
768
482
419
659
245
1599
923
879
99
47...

result:

ok 3000 lines

Test #16:

score: 2
Accepted
time: 25ms
memory: 8104kb

input:

3000 3000
0 265577685
0 279712461
0 865961338
0 715526160
0 152109041
0 720516447
0 663839583
0 572363102
0 15684570
0 774105531
0 355480679
0 318103883
0 809487980
0 566618853
0 399560845
0 428122875
0 406123722
0 227690500
0 306745648
0 787880089
0 156872708
0 469927843
0 869358593
0 484045893
0 4...

output:

216
312
0
4
0
2580
1282
0
0
2331
0
0
1108
0
710
1405
0
2129
0
0
1820
0
0
1698
0
1215
1389
0
0
2892
2456
2856
0
0
111
1849
205
0
795
0
0
0
2288
849
1432
927
0
0
227
1335
0
1565
17
398
1512
282
1611
0
2268
2894
0
337
0
277
2501
0
2182
0
21
0
1568
0
1706
1102
0
454
0
2457
0
0
0
0
0
0
0
1993
0
78
0
0
0
...

result:

ok 3000 lines

Test #17:

score: 2
Accepted
time: 25ms
memory: 8076kb

input:

3000 3000
905574076 0
62086925 0
984401157 0
900477115 0
688562084 0
607520732 0
679335141 0
4786510 0
595168939 0
16199355 0
932151269 0
333912126 0
772707530 0
544868665 0
863264108 0
492456951 0
971680943 0
930894040 0
405136186 0
728899221 0
800538513 0
145763793 0
544013589 0
250213891 0
317696...

output:

0
0
0
0
0
411
811
625
2171
0
0
0
1283
992
0
0
0
41
0
0
10
843
672
876
876
1217
2327
0
0
0
0
77
0
0
0
0
888
1891
563
0
1508
1284
1618
546
0
0
1391
0
688
270
989
106
0
0
1711
1461
0
1923
0
2260
435
0
0
1759
1353
0
0
843
1301
0
547
0
373
0
823
0
1864
492
0
0
0
0
1058
0
0
0
0
682
0
186
1198
0
544
1200
2...

result:

ok 3000 lines

Test #18:

score: 2
Accepted
time: 23ms
memory: 8056kb

input:

3000 3000
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
3000
0
0
0
3000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3000
0
3000
3000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3000 lines

Subtask #2:

score: 0
Time Limit Exceeded

Test #19:

score: 0
Time Limit Exceeded

input:

100000 100000
26753 11234
32815 62591
34318 93262
77179 57605
88208 33327
48449 99060
42403 58561
85715 7001
2418 90938
77409 6957
546 83283
53957 8374
49470 1483
65866 64950
4269 8745
19041 85833
22344 90706
92926 35603
54697 75311
72601 66401
77598 8193
3751 54202
32710 5877
23835 38264
34381 3338...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%