QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#326919#62. Examinationgubshig20 112ms8296kbC++172.9kb2024-02-14 14:05:112024-02-14 14:05:12

Judging History

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

  • [2024-02-14 14:05:12]
  • 评测
  • 测评结果:20
  • 用时:112ms
  • 内存:8296kb
  • [2024-02-14 14:05:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

constexpr int MX = 1e5 + 1e3;

struct BIT{
    int t[MX], sz = MX;

    BIT(){
        fill(t, t + MX, 0);
    }

    void update(int i, int v){
        while(i < MX){
            t[i] += v;
            i += (i & -i);
        }
    }

    int query(int i){
        int ret = 0;
        while(i){
            ret += t[i];
            i -= (i & -i);
        }
        return ret;
    }
};

int n, q, ans[MX];
bool flag[MX];
array<int, 3> s[MX];
array<int, 4> qs[MX];

void solvex(){
    sort(s + 1, s + 1 + n, [&](array<int, 3> a, array<int, 3> b){
        return a[0] > b[0];
    });
    sort(qs + 1, qs + 1 + q, [&](array<int, 4> a, array<int, 4> b){
        return a[0] > b[0];
    });

    BIT bit;
    int ptr = 1;
    for(int i = 1; i <= q; i++){
        while(ptr <= n && s[ptr][0] >= qs[i][0]){
            bit.update(s[ptr][2], 1);
            ptr++;
        }
        if(flag[qs[i][3]]) ans[qs[i][3]] += ptr - bit.query(qs[i][2] - 1) - 1;
    }
}

void solvey(){
    sort(s + 1, s + 1 + n, [&](array<int, 3> a, array<int, 3> b){
        return a[1] > b[1];
    });
    sort(qs + 1, qs + 1 + q, [&](array<int, 4> a, array<int, 4> b){
        return a[1] > b[1];
    });

    BIT bit, bitx;
    int ptr = 1;
    for(int i = 1; i <= q; i++){
        while(ptr <= n && s[ptr][1] >= qs[i][1]){
            bit.update(s[ptr][2], 1);
            bitx.update(s[ptr][0], 1);
            ptr++;
        }
        if(flag[qs[i][3]]) ans[qs[i][3]] += ptr - bit.query(qs[i][2] - 1) - 1;
        else ans[qs[i][3]] = ptr - bitx.query(qs[i][0] - 1) - 1;
    }
}

void solvez(){
    for(int i = 1; i <= q; i++){
        if(flag[qs[i][3]]) ans[qs[i][3]] -= n - qs[i][2] + 1;
    }
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    
    cin >> n >> q;
    vector<int> a, c;
    for(int i = 1; i <= n; i++){
        cin >> s[i][0] >> s[i][1];
        a.push_back(s[i][0]);
        c.push_back(s[i][0] + s[i][1]);
    }
    
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    for(int i = 1; i <= n; i++){
        s[i][2] = lower_bound(c.begin(), c.end(), s[i][0] + s[i][1]) - c.begin() + 1;
        s[i][0] = lower_bound(a.begin(), a.end(), s[i][0]) - a.begin() + 1;
    }

    for(int i = 1; i <= q; i++){
        cin >> qs[i][0] >> qs[i][1] >> qs[i][2];
        flag[i] = qs[i][0] + qs[i][1] < qs[i][2];
        qs[i][0] = lower_bound(a.begin(), a.end(), qs[i][0]) - a.begin() + 1;
        if(qs[i][2] > c.back()) qs[i][2] = n + 1;
        else qs[i][2] = lower_bound(c.begin(), c.end(), qs[i][2]) - c.begin() + 1;
        qs[i][3] = i;
    }

    solvex();
    solvey();
    solvez();

    for(int i = 1; i <= q; i++){
        cout << ans[i] << '\n';
    }
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4424kb

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
1
0
0
0
0
1
3
0

result:

wrong answer 3rd lines differ - expected: '2', found: '1'

Subtask #2:

score: 20
Accepted

Test #19:

score: 20
Accepted
time: 96ms
memory: 8296kb

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
13565
11736
28514
4108
33065
27851
26019
23511
12295
30617
229
20830
1461
3465
17020
36047
23196
69812
24530
13442
8259
24433
733
10411
20119
15897
75646
27339
73794
46246
61350
520
59415
6149
798
2836
4628
14774
40980
38231
7313
39010
14774
27553
20182
82757
35655
3811
29324
5084
6...

result:

ok 100000 lines

Test #20:

score: 0
Accepted
time: 101ms
memory: 8232kb

input:

100000 100000
36183 27642
41135 83584
70122 47356
53931 91393
18974 31405
24368 55518
10497 80811
48033 26530
64308 48589
68190 3786
2581 71927
88230 32477
43296 50536
88504 21426
14146 80077
53732 78665
79135 26660
86542 61452
4123 6597
44250 67766
56783 45985
22533 26926
52239 41762
51757 22717
67...

output:

73744
15573
3541
33582
45046
39539
8350
49949
26717
17310
51586
47422
27917
42623
22829
63447
17401
12617
46091
44926
33866
27094
2221
16429
18302
430
4537
875
22513
38949
3644
46728
7026
24266
328
41880
57894
6183
43148
17215
16219
28014
27938
50069
4104
1210
15102
25625
82753
23423
65093
5498
1715...

result:

ok 100000 lines

Test #21:

score: 0
Accepted
time: 100ms
memory: 8220kb

input:

100000 100000
61202 15303
17580 33912
58858 33470
70876 51214
84031 58237
23244 98448
65047 44425
49136 49506
40012 94044
68675 20279
42664 71753
45063 63883
66897 52949
47780 97851
31836 7559
22380 17745
24710 85337
35743 19683
82997 58382
58574 53595
47799 67394
90082 73911
39464 80374
38376 21112...

output:

1541
54000
34218
2175
8151
4219
8339
17842
16126
11861
20519
28683
35226
40705
46908
22901
3528
56957
16314
79164
844
23691
50609
44957
8551
62222
32891
859
48694
12759
24914
42690
672
81296
36765
1769
44302
3584
11073
10474
39060
17180
10162
48316
44979
43869
10455
10438
9888
51411
53010
5393
32677...

result:

ok 100000 lines

Test #22:

score: 0
Accepted
time: 95ms
memory: 8208kb

input:

100000 100000
71417 10
2561 2
98727 8
46876 8
47953 4
12675 7
42287 1
33941 1
85798 1
41398 8
22588 10
552 8
89891 5
82384 2
57149 3
28445 9
88248 8
88460 0
85250 7
71373 4
86754 9
89467 3
22493 6
6189 5
59883 0
63865 7
83979 8
48535 1
80407 3
36181 0
90781 1
99580 9
95056 1
276 0
34940 8
3059 0
327...

output:

3828
24801
13620
43570
70088
31578
8899
54600
1651
4502
18442
46620
15022
61296
30279
35147
5674
6413
57193
41261
28498
12570
1346
59248
12610
35555
7355
9293
46366
60596
3343
5118
8843
41436
13517
13785
55234
22798
56680
6933
66367
13924
15466
18014
5583
23109
4463
14174
9680
44018
24446
54065
9190...

result:

ok 100000 lines

Test #23:

score: 0
Accepted
time: 65ms
memory: 8228kb

input:

100000 100000
1 41869
9 19183
9 55137
1 85647
4 57461
10 52473
3 78990
9 57080
10 71084
2 76290
2 82919
4 93821
6 3994
8 11800
8 81833
6 66729
2 79529
3 73951
1 3288
4 49246
2 95984
0 76298
0 54478
0 28108
8 19171
8 18851
8 98271
0 98642
4 55247
6 53198
10 48223
1 37502
3 84842
8 37860
4 97053
6 981...

output:

36629
4922
38944
47314
59748
48310
779
20349
372
32987
50348
26069
3108
1436
13356
51963
11910
71350
31011
20695
1536
1645
21253
74319
18542
58746
2118
35286
21362
56522
30619
51319
11290
15157
49479
87630
42334
35111
37612
10421
8882
51232
6288
27008
43089
1225
79570
18817
8247
24811
48750
16065
29...

result:

ok 100000 lines

Test #24:

score: 0
Accepted
time: 47ms
memory: 8156kb

input:

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

output:

90980
4148
26481
66183
52352
1707
5010
11562
41513
4186
9905
44902
44902
39944
34933
37356
33122
24744
16533
66183
8260
63815
54738
41513
81968
27188
11601
74542
11562
39944
40738
46544
100000
41513
34933
19883
9192
100000
23187
3370
58145
26481
37356
40738
19820
27231
3321
33122
5870
34965
24902
59...

result:

ok 100000 lines

Test #25:

score: 0
Accepted
time: 89ms
memory: 8292kb

input:

100000 100000
16920 19840
10231 41386
38820 28123
22445 48220
65273 14725
54341 37461
37309 38346
89318 49204
17563 46620
6200 18547
8585 85811
4158 53520
5367 18135
45995 61479
60176 54604
69845 49932
34752 86343
54172 22714
67106 1791
81239 72100
52593 48897
33004 16395
27326 51396
76573 36715
904...

output:

43529
6180
65700
23480
40397
85154
85769
56441
90410
52044
74129
37519
32556
25470
8134
79327
73561
4137
20383
80319
29834
70473
666
90574
35292
47942
16929
41871
87875
51538
28277
38977
71837
89569
62619
73414
31188
6042
88365
135
87886
57374
51061
33869
73320
73986
833
46634
14497
55071
11607
6334...

result:

ok 100000 lines

Test #26:

score: 0
Accepted
time: 94ms
memory: 8164kb

input:

100000 100000
80510 30388
9721 43273
40267 87543
65390 76001
77038 15874
33199 77180
23703 73089
92577 83381
37244 27711
25511 93263
36203 51427
72191 29253
75585 81599
65961 80439
57254 55591
11526 36556
84158 68297
24375 75601
2424 16884
2486 15011
80114 75230
32317 60536
53661 27802
74904 32826
1...

output:

75225
22073
8677
12476
63971
34472
70152
62739
40445
45352
14682
24315
75913
55893
1911
91500
78728
95301
17042
49369
31943
28742
2189
79551
17655
50090
33004
10997
88916
42312
79437
79206
72337
22883
25894
55092
43626
91154
47019
7317
24756
29319
82474
1899
19612
13128
85857
9766
71916
74376
56771
...

result:

ok 100000 lines

Test #27:

score: 0
Accepted
time: 90ms
memory: 8296kb

input:

100000 100000
24722 64079
53023 15276
79634 88362
79225 25145
55071 51471
96159 84348
44084 10360
56846 4615
95408 85606
9622 15031
60868 44114
98814 10255
89674 21401
21512 50032
67875 21498
93831 45524
13730 92755
48841 68189
13543 24767
99085 83616
9261 40668
83802 17864
16220 72318
57846 59018
8...

output:

94286
85379
89888
91498
88313
83601
94402
84061
89279
92079
97216
88168
89994
84246
90897
85745
86351
87963
84359
87398
89211
88076
82636
90567
92707
84529
93362
87930
92259
84973
82940
85710
92502
94306
84133
89477
94688
88883
89635
87601
88472
84889
86317
92827
95789
91341
83802
90631
82365
85152
...

result:

ok 100000 lines

Test #28:

score: 0
Accepted
time: 58ms
memory: 8156kb

input:

100000 100000
0 87333
0 47306
0 73616
0 83810
0 58737
0 92470
0 76873
0 82155
0 71275
0 94285
0 84390
0 86081
0 48955
0 62659
0 7736
0 61906
0 35018
0 64239
0 83486
0 45630
0 33826
0 54456
0 74126
0 32328
0 90642
0 52130
0 47228
0 74867
0 40395
0 40579
0 82415
0 1211
0 21030
0 24189
0 3690
0 98386
0...

output:

0
0
0
0
0
0
97463
0
0
0
0
0
0
65532
0
93513
11054
0
24870
87413
14693
59413
96405
0
75773
39653
0
61698
0
0
52126
0
0
55595
70498
81181
0
97398
25199
0
0
48286
52988
0
85327
64978
64451
0
0
0
28171
0
71231
0
57581
0
0
18457
0
41176
0
0
0
28454
0
58910
88736
0
20802
86195
0
0
4950
0
0
15907
0
0
0
0
5...

result:

ok 100000 lines

Test #29:

score: 0
Accepted
time: 85ms
memory: 8280kb

input:

100000 100000
1265 0
66200 0
23977 0
67462 0
2582 0
21654 0
96330 0
83421 0
43548 0
20762 0
63237 0
18611 0
81518 0
38930 0
65200 0
27472 0
16764 0
98231 0
369 0
19043 0
91768 0
37924 0
12639 0
9034 0
46618 0
78051 0
4952 0
27008 0
15869 0
76420 0
81000 0
46122 0
61780 0
4881 0
26128 0
81569 0
70762...

output:

0
0
53648
0
0
74532
90
48308
0
0
31128
62682
0
0
89790
68851
5421
0
0
0
11086
0
0
20888
0
0
0
0
51238
0
98603
74339
0
51949
0
43895
80241
0
0
0
62659
79786
18550
12654
0
66825
42309
77425
0
34366
41806
51554
0
37090
14922
0
0
0
0
66148
78242
0
0
2768
98798
0
0
0
83697
0
0
0
94656
0
41872
34920
3357
...

result:

ok 100000 lines

Test #30:

score: 0
Accepted
time: 30ms
memory: 8212kb

input:

100000 100000
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
100000
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
100000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100000
0
0
0
0
0
100000
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
100000
0
0
0
0
0
0
0
0
100000
0
0
0
0
0
0
0
0
0
0
0
0
0
100000
0
0
10000...

result:

ok 100000 lines

Subtask #3:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #31:

score: 0
Wrong Answer
time: 112ms
memory: 8052kb

input:

100000 100000
92665 39585
18318 75712
55464 95016
91413 92286
1143 98091
80611 74738
79009 23540
38987 57835
29236 84070
82706 4071
66995 63808
18498 12274
49964 24682
74388 38237
22999 67441
3612 47396
47896 58014
6258 1844
19088 60890
61212 68488
41162 8272
31552 39640
59441 18422
29743 72631
9780...

output:

12083
80940
8100
2723
7319
-25859
21474
-21825
19650
-22661
10877
-20850
-20031
-23193
-8273
11040
4526
21728
23691
7889
14421
5944
96
16653
2990
-26138
-24040
604
47470
1042
-26038
82
2069
-24221
-25866
17707
2900
18460
7886
12892
8605
2309
20125
31534
7825
-19954
-26198
17324
5709
15433
26870
91
1...

result:

wrong answer 1st lines differ - expected: '26052', found: '12083'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%