QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746679#62. ExaminationShumomo0 139ms12360kbC++141.8kb2024-11-14 15:15:422024-11-14 15:15:42

Judging History

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

  • [2024-11-14 15:15:42]
  • 评测
  • 测评结果:0
  • 用时:139ms
  • 内存:12360kb
  • [2024-11-14 15:15:42]
  • 提交

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-1;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-1;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=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].a++;
        x[i].b++;
        x[i].c++;
        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: 0
Wrong Answer

Test #1:

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

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: 8048kb

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: 0ms
memory: 7872kb

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: 8052kb

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: 7864kb

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: 1ms
memory: 8056kb

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: 5ms
memory: 7952kb

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: 5ms
memory: 7960kb

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: 5ms
memory: 10068kb

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: 0
Wrong Answer
time: 4ms
memory: 8008kb

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:

428
147
801
525
766
100
21
966
154
719
599
771
1667
1440
235
473
724
960
590
126
1112
16
535
423
575
836
119
469
976
35
335
966
641
1646
236
103
14
996
276
567
2241
1251
280
375
1299
47
222
331
13
363
185
49
355
587
1566
321
1928
67
814
368
473
232
1768
959
99
175
1470
0
388
255
754
131
598
1248
646...

result:

wrong answer 1st lines differ - expected: '381', found: '428'

Subtask #2:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 139ms
memory: 12360kb

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:

3392
12465
20237
13566
11736
28515
4108
33065
27852
26019
23511
12296
30617
230
20831
1461
3465
17020
36047
23197
69812
24530
13443
8259
24435
733
10412
20119
15898
75646
27340
73796
46246
61350
520
59415
6149
798
2836
4629
14775
40982
38232
7313
39010
14774
27554
20183
82759
35655
3811
29324
5084
6...

result:

wrong answer 4th lines differ - expected: '13565', found: '13566'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%