QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#534075#62. Examinationisirazeev0 469ms50456kbC++202.7kb2024-08-26 20:18:532024-08-26 20:18:54

Judging History

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

  • [2024-08-26 20:18:54]
  • 评测
  • 测评结果:0
  • 用时:469ms
  • 内存:50456kb
  • [2024-08-26 20:18:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long

struct Node {
    int a, b, c, ind, cost;
};

struct BIT {
    vector<int> f;
    int N;

    void init(int n) {
        N = n + 2;
        f.resize(n + 2, 0);
    }

    void update(int i, int val) {
        for (; i < N; i += (i & (-i)))
            f[i] += val;
    }

    int sum(int r) {
        int res = 0;
        for (; r > 0; r -= (r & (-r)))
            res += f[r];
        return res;
    }
};

const int N = (int) 1e6 + 10;

vector<Node> v;
int ans[N];

BIT bit;

void DivideAndConquer(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2, a = l, b = mid + 1, sum = 0;
    DivideAndConquer(l, mid), DivideAndConquer(mid + 1, r);
    vector<pair<int, int>> record;
    vector<Node> tmp;
    while (a <= mid && b <= r) {
        if (v[a].b >= v[b].b) {
            bit.update(v[a].c, v[a].cost), record.emplace_back(v[a].c, v[a].cost);
            sum += v[a].cost, tmp.emplace_back(v[a++]);
        } else {
            ans[v[b].ind] += sum - bit.sum(v[b].c - 1), tmp.emplace_back(v[b++]);
        }
    }
    while (a <= mid) tmp.emplace_back(v[a++]);
    while (b <= r) ans[v[b].ind] += sum - bit.sum(v[b].c - 1), tmp.emplace_back(v[b++]);
    for (int i = 0; i < (int) tmp.size() - 1; i++)
        if (tmp[i].b < tmp[i + 1].b) exit(-1);
    for (auto [ind, val]: record) bit.update(ind, -val);
    for (int i = l; i <= r; i++) v[i] = tmp[i - l];
}

set<int> all;
map<int, int> to;

void compress(vector<int> &a) {
    all.clear(), to.clear();
    int cnt = 1;
    for (int i: a) all.insert(i);
    for (int i: all) to[i] = cnt++;
    for (int &i: a) i = to[i];
}

void solve() {
    vector<int> A, B, C;
    for (Node i: v) A.emplace_back(i.a), B.emplace_back(i.b), C.emplace_back(i.c);
    compress(A), compress(B), compress(C);
    for (int i = 0; i < (int) v.size(); i++) v[i].a = A[i], v[i].b = B[i], v[i].c = C[i];
    int mx = 0;
    for (int i = 0; i < (int) v.size(); i++) mx = max({mx, v[i].a, v[i].b, v[i].c});
    bit.init(mx + 1);
    sort(v.begin(), v.end(), [&](Node a, Node b) {
        return (a.a != b.a ? a.a > b.a : (a.b != b.b ? a.b > b.b : a.c > b.c));
    });
    DivideAndConquer(0, (int) v.size() - 1);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int s, t;
        cin >> s >> t;
        v.emplace_back(s, t, s + t, q + i, 1);
    }
    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        v.emplace_back(x, y, z, i, 0);
    }
    solve();
    for (int i = 0; i < q; i++)
        cout << ans[i] << "\n";
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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

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

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

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

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

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: 10ms
memory: 4892kb

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: 10ms
memory: 4820kb

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: 10ms
memory: 4840kb

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: 9ms
memory: 5024kb

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: 8ms
memory: 4852kb

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

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
2144
338
510
116
215
1550
1163
132
892
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
468
784
294
91
660
132
739
983
1087
195
1319
273
583
33
1932
876
146
365
371
203
59...

result:

wrong answer 14th lines differ - expected: '2158', found: '2144'

Subtask #2:

score: 0
Wrong Answer

Test #19:

score: 20
Accepted
time: 465ms
memory: 47964kb

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: 20
Accepted
time: 469ms
memory: 47280kb

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: 20
Accepted
time: 453ms
memory: 47336kb

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: 20
Accepted
time: 352ms
memory: 50456kb

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: 20
Accepted
time: 355ms
memory: 47852kb

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
Wrong Answer
time: 102ms
memory: 37908kb

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
99527
41513
34933
19883
9192
99528
23187
3370
58145
26481
37356
40738
19820
27231
3321
33122
5870
34965
24902
5975...

result:

wrong answer 33rd lines differ - expected: '100000', found: '99527'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%