QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#534068#62. Examinationisirazeev0 164ms10936kbC++202.2kb2024-08-26 20:16:152024-08-26 20:16:15

Judging History

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

  • [2024-08-26 20:16:15]
  • 评测
  • 测评结果:0
  • 用时:164ms
  • 内存:10936kb
  • [2024-08-26 20:16:15]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = (int) 1e5 * 2 + 10;

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

const int NN = (int)1e18;

struct BIT {
    map<int, int> f;

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

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

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 (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() {
    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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

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

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

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

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

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

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

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: 161ms
memory: 10936kb

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: 164ms
memory: 10876kb

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: 152ms
memory: 10864kb

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: 143ms
memory: 10584kb

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: 163ms
memory: 10568kb

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
Time Limit Exceeded

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:


result:


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:

0%