QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#762566#9559. The TowerpropaneAC ✓1226ms579888kbC++202.8kb2024-11-19 15:32:482024-11-19 15:32:52

Judging History

你现在查看的是测评时间为 2024-11-19 15:32:52 的历史记录

  • [2024-11-20 09:05:16]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果：AC
  • 用时：1229ms
  • 内存：581208kb
查看
  • [2024-11-20 08:41:35]
  • hack成功，自动添加数据
  • (/hack/1205)
  • [2024-11-19 15:32:52]
  • 评测
  • 测评结果：100
  • 用时：1226ms
  • 内存：579888kb
查看
  • [2024-11-19 15:32:48]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<ranges>
#include<map>
using namespace std;
using LL = long long;

const int maxn = 5e5 + 5;
struct Node{
    int cnt, l, r, p, tag;
}tr[maxn * 128];
int root[maxn], idx;
map<int, int> pos, color;

void pushup(int u){
    tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;
    if (tr[u].l) tr[tr[u].l].p = u;
    if (tr[u].r) tr[tr[u].r].p = u;
}

void update(int u, int l, int r, int x){
    tr[u].tag = x;
    tr[u].cnt = (r - l + 1) * x;
}

void pushdown(int u, int l, int r){
    if (tr[u].tag){
        if (!tr[u].l) tr[u].l = ++idx;
        if (!tr[u].r) tr[u].r = ++idx;
        int mid = (l + r) / 2;
        update(tr[u].l, l, mid, tr[u].tag);
        update(tr[u].r, mid + 1, r, tr[u].tag);
        tr[u].tag = 0;
    }
}

void get(int &u, int l, int r, int x){
    if (!u) u = ++idx;
    if (l == r){
        pos[x] = u;
        return;
    }
    pushdown(u, l, r);
    int mid = (l + r) / 2;
    if (x <= mid) get(tr[u].l, l, mid, x);
    else get(tr[u].r, mid + 1, r, x);
    pushup(u);
}

int split(int &u, int l, int r, int &k){
    if (k == 0 or u == 0) return 0;
    int ret = ++idx;
    if (tr[u].cnt <= k){
        k -= tr[u].cnt;
        ret = u;
        u = 0;
        return ret;
    }
    pushdown(u, l, r);
    int mid = (l + r) / 2;
    tr[ret].l = split(tr[u].l, l, mid, k);
    tr[ret].r = split(tr[u].r, mid + 1, r, k);
    pushup(u);
    pushup(ret);
    return ret;
}

int merge(int x, int y, int l, int r){
    if (x == 0 or y == 0) return x + y;
    if (l == r){
        tr[x].cnt += tr[y].cnt;
        return x;
    }
    // pushdown(x, l, r);
    // pushdown(y, l, r);
    int mid = (l + r) / 2;
    tr[x].l = merge(tr[x].l, tr[y].l, l, mid);
    tr[x].r = merge(tr[x].r, tr[y].r, mid + 1, r);
    pushup(x);
    return x;
}

int query(int x){
    int u = pos[x];
    while(tr[u].p) u = tr[u].p;
    return color[u];
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const int N = 1e9;
    root[0] = ++idx;
    color[root[0]] = 0;
    update(root[0], 1, N, 1);
    int n;
    cin >> n;
    vector<pair<int, int> > ops(n);
    for(auto &[op, x] : ops){
        cin >> op >> x;
        if (op == 3) get(root[0], 1, N, x);
    }
    int cnt = 0;
    for(auto [op, x] : ops){
        if (op == 1){
            x = min(x, tr[root[0]].cnt);
            root[++cnt] = split(root[0], 1, N, x);
            color[root[cnt]] = cnt;
        }
        else if (op == 2){
            root[0] = merge(root[0], root[x], 1, N);
            color[root[0]] = 0;
        }
        else{
            cout << query(x) << '\n';
        }
    }

}
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5656kb

input:

7
1 2
1 4
3 3
2 1
3 2
1 4
3 7

output:

2
0
3

result:

ok 3 number(s): "2 0 3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

5
3 6
3 8
1 2
1 5
3 2

output:

0
0
1

result:

ok 3 number(s): "0 0 1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5896kb

input:

500
1 17
2 1
3 2
3 17
1 14
1 20
1 15
2 4
1 11
3 72
1 15
3 5
3 79
1 19
2 6
2 2
1 10
3 77
2 5
2 3
3 8
2 7
2 8
3 101
1 16
2 9
3 91
3 61
1 11
3 45
1 9
1 13
1 20
1 19
3 142
2 14
2 11
1 7
3 98
1 3
1 5
1 9
3 119
3 136
1 20
1 7
1 3
1 6
3 106
1 2
2 13
2 17
2 19
3 232
1 19
2 15
3 207
3 264
2 24
1 19
2 12
3 11...

output:

0
0
0
2
0
7
8
0
0
0
0
0
0
0
0
0
0
0
0
0
25
0
0
0
0
0
0
33
0
0
0
0
0
0
0
0
0
0
0
0
52
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
70
0
0
0
0
0
0
0
0
0
0
0
0
0
92
0
95
0
0
0
0
0
0
0
0
0
0
0
102
0
0
0
0
0
0
0
0
0
0
0
0
0
111
0
0
0
0
0
0
120
0
0
0
0
0
0
0
0
0
0
0
0
0
99
0
0
0
0
0
131
133
0
0
0
0
0
117
0
0
0
0
0...

result:

ok 164 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 5696kb

input:

500
3 1
3 1
3 1
3 1
3 1
1 4412412
1 10247266
1 14616289
3 13925896
1 44094358
2 4
3 16963583
1 29167079
1 71445446
3 121523866
1 9541088
2 6
2 7
3 143236216
2 2
3 156313828
1 33267424
3 100714325
3 15092860
3 89601770
2 8
3 201789970
1 30507527
2 5
1 67021830
3 234973560
1 10823444
1 19147051
1 7218...

output:

0
0
0
0
0
2
3
6
0
0
0
3
0
0
0
0
0
0
13
0
16
17
11
17
0
0
0
0
0
0
0
19
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
0
0
0
45
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
57
57
53
53
53
0
63
0
66
0
0
62
62
72
0
0
53
0
81
69
64
80
53
74
53
81
81
69
90
80
65
95
96
92
0
53
0
101
93
81
103
105
0
102
74
105
74
81
105
93
69
119
1...

result:

ok 174 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 5576kb

input:

500
3 1
3 1
3 1
1 320269189
1 948169162
1 351870928
1 913315720
2 4
1 165426182
1 539661032
3 842094943
3 726768630
1 585756645
1 327182255
3 928037381
3 819034974
3 749190162
3 676969663
2 2
1 802722944
1 848855782
3 227383778
1 725550812
3 892603437
1 451994900
3 470357939
2 1
1 598424975
3 786248...

output:

0
0
0
2
2
2
2
2
2
1
9
9
9
9
0
9
9
9
9
9
0
0
0
0
0
0
0
0
0
0
0
19
0
20
20
24
24
24
24
32
31
0
26
33
38
26
38
32
32
38
38
38
26
38
38
54
38
26
38
38
26
38
38
54
54
54
54
54
65
65
65
67
54
67
54
0
0
70
0
70
72
0
0
0
0
0
0
0
0
0
0
0
78
78
0
0
82
82
0
84
83
84
0
0
87
87
87
87
93
96
96
96
0
0
0
0
0
100
10...

result:

ok 173 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 5624kb

input:

6
3 1
1 3
3 3
1 3
2 2
1 6

output:

0
1

result:

ok 2 number(s): "0 1"

Test #7:

score: 0
Accepted
time: 470ms
memory: 139364kb

input:

500000
3 1
1 5
2 1
3 2
1 10
1 18
1 16
1 15
1 20
2 2
3 8
3 4
2 6
2 5
2 3
1 13
3 16
2 7
2 4
3 34
1 12
1 11
2 8
3 18
3 97
1 7
3 128
3 13
2 9
2 10
3 81
3 48
1 5
2 11
1 4
2 12
1 5
1 15
1 13
2 14
2 15
1 3
1 6
2 16
3 141
2 17
1 6
2 13
2 18
1 10
1 12
3 102
2 20
1 11
3 86
1 7
3 176
2 21
1 5
3 92
1 14
2 22
1 ...

output:

0
0
0
0
0
0
9
0
0
9
0
0
0
0
0
0
0
0
0
0
39
0
0
0
0
0
39
0
0
0
0
0
0
35
0
49
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
86
0
0
0
0
0
0
0
0
0
94
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
127
134
128
0
0
0
0
0
128
0
0
0
0
0
133
0
0
0
0
0
0
0
0
...

result:

ok 167358 numbers

Test #8:

score: 0
Accepted
time: 397ms
memory: 128756kb

input:

500000
3 1
1 34999032
2 1
3 20479366
3 16132210
3 10950706
3 27656988
3 18181558
3 20096893
1 83795773
3 113805204
3 115628116
1 42488647
1 42211622
2 3
1 92268056
2 2
1 80060142
2 4
1 49696107
3 299966231
3 365132652
1 46139635
1 64375123
2 8
3 39930760
1 14908781
3 210153892
1 85648326
3 568835561...

output:

0
0
0
0
0
0
0
0
0
0
0
6
5
0
5
6
0
0
0
0
0
0
18
0
6
0
19
18
18
19
0
0
0
23
0
21
0
24
0
28
0
0
0
34
0
37
38
39
0
0
0
0
0
0
43
0
0
49
48
43
0
0
43
48
0
0
55
0
55
58
0
0
0
0
0
0
0
0
68
0
0
0
0
0
0
0
77
72
86
75
0
72
0
82
0
0
0
0
0
92
0
106
0
106
92
0
0
0
0
0
0
0
0
0
0
0
0
126
0
0
0
0
0
130
0
0
0
138
0
0...

result:

ok 166515 numbers

Test #9:

score: 0
Accepted
time: 345ms
memory: 101652kb

input:

500000
3 1
3 1
3 1
1 85593529
3 57891556
2 1
3 38559908
1 727251945
1 815334095
1 988926819
3 107155104
1 724052442
3 63908582
2 5
2 4
1 84610655
2 2
3 2423402
3 853118582
1 448879846
2 6
2 3
1 815614446
2 8
1 674635945
2 7
1 46140898
3 820338862
2 10
1 692524546
2 11
1 625079933
1 482471788
3 44351...

output:

0
0
0
1
0
2
2
0
3
9
12
9
9
9
21
9
21
21
0
0
0
21
27
27
30
28
30
28
0
28
38
42
28
43
43
38
43
45
45
45
51
47
47
45
47
51
51
45
51
68
51
51
45
45
68
45
47
45
47
45
45
51
80
0
81
81
81
81
81
81
0
0
0
0
84
84
85
84
85
84
84
84
84
84
0
0
0
95
95
95
95
95
99
98
99
95
98
95
98
98
98
95
95
98
95
103
111
111...

result:

ok 166286 numbers

Test #10:

score: 0
Accepted
time: 39ms
memory: 9140kb

input:

500000
1 39567744
1 957918384
1 896336073
1 302217145
1 328404139
1 984894105
1 428308004
1 67268263
1 619517065
1 186724562
1 165376000
1 253795867
1 721330183
1 433623064
1 20169195
1 288503667
1 791272786
1 526657641
1 638212274
1 501209932
1 320898519
1 288747265
1 581193313
1 497930627
1 423401...

output:

result:

ok 0 number(s): ""

Test #11:

score: 0
Accepted
time: 480ms
memory: 485332kb

input:

500000
1 198
1 267
1 305
1 955
2 3
1 242
1 854
3 1322
1 337
1 830
1 838
1 703
1 81
1 667
1 591
1 152
1 308
1 326
1 237
1 362
1 199
1 252
1 910
3 2543
2 12
1 90
1 646
1 444
1 520
1 206
1 283
1 207
1 793
1 236
1 681
1 21
1 470
1 625
1 326
2 25
1 916
1 922
1 614
1 317
1 399
1 508
3 12977
1 368
1 558
1 ...

output:

4
7
33
46
57
57
104
10
0
43
0
50
137
162
169
220
73
108
44
86
154
41
213
192
0
125
331
52
472
58
165
558
547
0
430
234
628
330
625
54
409
703
0
613
498
258
702
282
418
346
171
667
0
650
722
9
739
88
471
542
340
253
401
479
490
399
1082
817
1121
449
807
1121
641
797
20
1327
351
810
1337
1208
783
620
...

result:

ok 25227 numbers

Test #12:

score: 0
Accepted
time: 474ms
memory: 263932kb

input:

500000
1 249
1 435
2 2
1 48
2 3
2 1
1 510
2 4
1 626
2 5
1 831
3 1996
1 237
1 759
2 8
3 2585
1 155
1 601
1 665
1 803
2 9
2 10
2 6
2 7
1 114
1 605
1 895
1 155
2 16
1 625
2 13
2 17
1 242
1 15
3 3636
2 11
2 14
3 3530
3 6827
2 12
1 356
1 615
1 148
1 331
3 785
1 275
1 794
1 596
1 495
2 23
1 140
2 20
1 238...

output:

0
0
0
0
0
15
0
0
26
0
0
0
0
0
94
0
0
113
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
117
162
0
213
194
0
117
0
0
0
249
211
0
0
0
0
0
0
287
0
0
290
0
267
0
166
0
0
243
349
0
266
327
0
338
338
0
0
0
336
0
0
0
0
0
0
0
0
401
0
0
375
416
371
343
258
0
0
0
0
0
0
0
0
462
0
0
0
0
462
0
0
452
0
0
0
0
411
0
456
0
0
0
498...

result:

ok 49640 numbers

Test #13:

score: 0
Accepted
time: 128ms
memory: 40068kb

input:

500000
1 325663181
1 341421661
2 1
2 2
1 798695561
1 789604791
2 3
1 752705846
1 271837520
1 2324300
1 156465725
1 552978643
1 704305136
3 708781692
1 538026101
1 554055497
1 551799143
1 928267539
1 162992249
1 178671365
1 41327601
1 34105375
3 583284520
2 4
1 335357707
2 18
2 13
1 351743555
2 11
1 ...

output:

5
5
6
5
5
5
5
5
42
67
42
67
66
82
82
82
0
82
82
94
99
94
82
114
82
94
82
82
82
67
94
94
94
0
67
0
94
148
149
67
149
149
149
149
149
149
149
158
158
149
67
0
213
158
214
214
214
214
214
213
158
214
158
232
265
264
158
158
265
264
305
265
280
232
265
264
265
265
331
265
265
264
325
264
264
331
295
264...

result:

ok 49895 numbers

Test #14:

score: 0
Accepted
time: 862ms
memory: 337368kb

input:

500000
3 1
1 208
1 44
1 519
1 107
3 587
3 745
3 158
3 364
3 120
1 232
1 101
1 879
3 517
3 882
3 1383
1 877
3 876
3 2890
1 597
1 938
3 221
1 882
1 423
3 4211
1 954
1 849
1 159
3 5130
3 2488
1 186
3 6193
1 211
1 783
1 476
1 411
1 469
3 5038
3 3069
1 145
2 4
3 8960
3 4781
1 216
3 9895
1 863
1 740
1 70
...

output:

0
3
3
1
3
1
3
5
7
4
8
2
10
11
8
13
11
9
19
11
21
9
7
11
10
7
3
11
25
18
9
19
28
28
25
34
38
31
29
24
11
14
34
21
42
32
21
28
11
7
47
7
11
27
37
55
10
50
49
52
39
8
21
55
64
38
3
34
10
65
32
69
31
61
36
5
10
10
7
34
0
70
79
55
10
1
27
19
50
45
12
38
63
34
9
65
0
72
24
75
68
27
25
66
62
57
84
50
24
80...

result:

ok 224721 numbers

Test #15:

score: 0
Accepted
time: 1131ms
memory: 200492kb

input:

500000
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 495045 numbers

Test #16:

score: 0
Accepted
time: 441ms
memory: 204168kb

input:

500000
1 398
1 645
2 2
1 985
2 3
2 1
1 240
2 4
1 856
2 5
1 469
1 729
1 298
2 7
2 8
2 6
1 944
2 9
1 490
2 10
1 404
1 599
2 11
1 693
1 791
1 762
1 73
2 14
2 12
1 904
2 15
2 17
1 627
2 16
1 200
1 170
2 20
1 611
2 13
1 879
1 270
2 18
2 23
1 575
2 19
1 377
2 25
2 24
2 22
2 21
1 971
2 26
1 118
1 224
2 28
...

output:

45
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
497
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 9965 numbers

Test #17:

score: 0
Accepted
time: 1216ms
memory: 244408kb

input:

500000
3 863503832
3 285813354
3 414051174
3 97666985
3 466272422
3 448257369
3 956137762
3 387839447
3 504996933
3 971922171
3 737655581
3 914663293
3 431235168
3 598801556
3 197441204
1 9085
3 18435039
1 28953
3 240290602
3 660593544
3 278294539
3 760061094
3 947453399
3 182070243
3 222738570
3 93...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 460003 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 5672kb

input:

5
1 1000000000
2 1
3 1000000000
1 1000000000
3 1000000000

output:

0
2

result:

ok 2 number(s): "0 2"

Test #19:

score: 0
Accepted
time: 1ms
memory: 5848kb

input:

1
3 11451419

output:

0

result:

ok 1 number(s): "0"

Test #20:

score: 0
Accepted
time: 275ms
memory: 166212kb

input:

500000
1 469
1 27403
1 8011
1 3666
3 431375941
1 5586
1 2876
1 911
1 8549
1 5022
1 11870
1 13676
1 14008
1 7714
1 5558
1 23433
1 5420
1 6330
1 1234
1 21150
1 15806
1 10289
1 638
1 1291
1 5427
1 304
1 7921
1 5709
1 586
1 3002
1 12144
1 5379
1 21367
1 10314
1 15571
1 21493
1 2691
1 7216
1 762
1 7791
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
324
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2181
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1723
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
54
0
0
0...

result:

ok 20003 numbers

Test #21:

score: 0
Accepted
time: 238ms
memory: 162976kb

input:

500000
1 2869
1 11476
1 2081
1 3225
1 6496
1 11473
1 4014
1 3439
1 13952
1 4133
1 4627
1 3486
1 24176
1 1103
1 15107
1 19628
1 1634
1 604
1 1669
1 12717
1 5305
1 17384
1 13159
1 574
1 11642
1 876
1 23211
1 26850
1 9274
1 3403
1 4044
1 5642
1 6203
1 1352
1 5604
1 969
1 4262
1 29813
1 11471
1 3397
1 3...

output:

24734
167977
249999

result:

ok 3 number(s): "24734 167977 249999"

Test #22:

score: 0
Accepted
time: 763ms
memory: 304736kb

input:

500000
1 471049
3 210537770
3 174642262
3 409419351
1 117066
1 33053
1 13142
3 181598847
1 129357
1 37381
1 197686
3 478570811
1 58776
1 14683
1 151018
3 51491818
1 138638
1 85547
1 188477
1 757
1 3848
1 53283
1 77145
1 29393
1 91077
1 132182
3 167622476
1 110618
1 29202
1 133185
1 33985
3 436250120...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
82
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
106
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
87
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200002 numbers

Test #23:

score: 0
Accepted
time: 425ms
memory: 331580kb

input:

500000
1 159000
1 13720
1 6590
1 59370
1 220632
1 513661
1 609
1 104291
1 3779
1 56248
1 189477
1 150404
1 10964
1 77315
1 135285
1 141171
1 16173
1 180444
1 97299
1 157409
1 14352
1 25243
1 10016
1 180301
1 32208
1 91019
1 105454
1 59531
1 501
1 139128
1 104096
1 4905
1 708069
1 213704
1 28070
1 31...

output:

0
0
0
0
0
0
0
0
255
0
0
0
0
299
0
590
0
0
0
0
0
0
0
0
0
0
0
0
0
0
361
0
0
0
0
0
956
0
0
1736
1063
0
0
1392
0
2222
0
0
0
1418
0
0
1744
2445
0
2488
0
0
681
186
0
0
329
0
2573
0
438
0
0
0
0
0
1000
0
2463
0
1488
0
0
0
1533
3115
3493
0
0
3494
0
590
0
0
0
0
0
3392
0
709
0
2856
0
0
3898
266
0
0
0
2947
2867...

result:

ok 10002 numbers

Test #24:

score: 0
Accepted
time: 350ms
memory: 388468kb

input:

500000
1 7530
1 5375
1 1583
1 10219
1 1563
1 1637
1 9573
1 1527
1 519
1 907
1 3795
1 6745
1 3936
1 4545
1 2291
1 599
1 617
1 3527
1 3061
1 1749
1 1944
1 4604
1 122
1 7561
1 1225
1 350
1 605
1 7258
1 242
1 428
1 1349
1 519
1 4304
1 1632
1 1073
1 1218
1 716
1 3848
1 538
1 3270
1 2546
1 1623
1 3093
1 2...

output:

0
0
0
0
0
0
53265
52394
0
0
0
0
0
0
65065
92942
0
0
23935
0
117540
0
0
169499
0
0
20825
97207
4208
0
0
94282
80833
0
0
190036
0
49502
0
0
141569
73882
0
0
28789
0
391
99126
255997
207625
11835
38585
276369
27212
141749
105272
143287
206441
59980
100724
182350
300990
0
221882
13051
187940
143694
1064...

result:

ok 101 numbers

Test #25:

score: 0
Accepted
time: 316ms
memory: 392792kb

input:

500000
1 2652
1 534
1 2173
1 350
1 776
1 9854
1 1849
1 5884
1 2083
1 2706
1 7416
1 379
1 2734
1 5024
1 108
1 835
1 6766
1 2331
1 3167
1 7043
1 4438
1 88
1 715
1 386
1 7707
1 12583
1 1037
1 361
1 2641
1 1840
1 2241
1 5368
1 5803
1 2963
1 2002
1 1577
1 2601
1 931
1 3026
1 1192
1 717
1 80
1 3971
1 36
1...

output:

59154
0
0
215216
242549
177051

result:

ok 6 numbers

Test #26:

score: 0
Accepted
time: 416ms
memory: 212920kb

input:

500000
1 2
1 2
3 2
3 5
2 1
1 4
1 9
2 3
1 6
1 3
2 5
1 8
1 1
2 7
1 9
1 1
2 9
1 14
1 1
3 25
2 11
1 15
1 1
2 13
1 16
1 3
2 15
1 20
1 4
2 17
1 23
1 1
2 19
1 27
1 1
2 21
1 31
1 2
2 23
3 86
1 35
1 1
2 25
1 40
3 526
1 1
2 27
1 41
1 5
3 499
2 29
1 45
1 1
2 31
1 46
1 6
2 33
1 53
1 1
2 35
1 55
1 1
2 37
3 290
1...

output:

1
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
310
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
859
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 50000 numbers

Test #27:

score: 0
Accepted
time: 480ms
memory: 218316kb

input:

500000
1 1
1 1
2 1
1 2
1 1
2 3
1 5
1 1
3 2
2 5
1 6
3 22
3 29
1 3
3 4
2 7
3 31
1 7
1 2
3 7
2 9
1 8
3 39
1 1
2 11
3 13
1 11
1 1
2 13
1 13
1 1
2 15
3 65
1 14
1 3
2 17
1 17
1 3
3 15
2 19
1 18
1 1
2 21
1 21
1 2
3 256
2 23
1 22
1 1
3 299
3 165
2 25
1 23
1 1
2 27
3 133
1 24
1 1
3 195
2 29
1 26
1 3
2 31
1 2...

output:

2
0
0
4
0
9
0
0
0
10
0
0
0
0
0
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
42
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 100000 numbers

Test #28:

score: 0
Accepted
time: 446ms
memory: 197544kb

input:

500000
1 1
1 1
3 82936
2 1
1 2
1 1
2 3
1 3
1 1
2 5
1 4
1 1
2 7
1 5
3 1415
1 1
2 9
1 6
3 45737
3 103035
3 74547
1 1
3 66256
3 8539
2 11
1 7
3 127811
1 1
3 119207
2 13
1 8
3 8066
1 1
2 15
1 9
1 1
2 17
1 10
1 1
2 19
1 11
1 1
3 30227
2 21
1 12
1 1
2 23
1 13
3 120832
1 1
2 25
1 14
1 1
3 68095
3 98568
2 2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 106787 numbers

Test #29:

score: 0
Accepted
time: 336ms
memory: 233200kb

input:

500000
1 1
1 1
2 1
1 2
1 1
2 3
1 3
1 1
2 5
1 4
1 1
2 7
3 81250
1 5
1 1
2 9
1 6
1 1
2 11
1 7
1 1
2 13
1 8
1 1
2 15
1 9
1 1
2 17
1 10
1 1
2 19
1 11
1 1
2 21
1 12
3 32637
1 1
2 23
1 13
1 1
2 25
1 14
1 1
2 27
1 15
1 1
3 105337
2 29
1 16
1 1
2 31
1 17
1 1
2 33
1 18
1 1
2 35
1 19
1 1
2 37
1 20
1 1
2 39
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
250
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 19985 numbers

Test #30:

score: 0
Accepted
time: 1022ms
memory: 134396kb

input:

500000
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499516 numbers

Test #31:

score: 0
Accepted
time: 1185ms
memory: 227340kb

input:

500000
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
1 62492
3 48564
3 53972
3 58895
3 22522
3 51135
3 41461
3 55004
3 28281
3 437...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 489886 numbers

Test #32:

score: 0
Accepted
time: 1226ms
memory: 253652kb

input:

500000
3 1
3 1
3 1
3 1
3 1
3 1
3 1
1 18450
3 14728
3 16406
3 11557
3 17169
3 11487
3 15297
3 17123
3 11132
3 18023
3 1430
3 12177
1 86902
1 17254
3 59286
3 3672
3 35650
3 99347
3 7143
3 110044
3 26590
3 76721
3 52658
3 46320
3 90002
3 102691
3 108407
3 70488
3 105068
3 99678
1 93326
3 138355
3 10002...

output:

0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
2
1
2
2
1
3
2
2
2
2
2
2
3
2
2
2
4
2
2
2
2
1
2
2
4
4
2
4
2
5
3
2
2
2
2
4
5
2
6
6
2
6
2
2
4
6
5
4
1
4
4
4
2
2
6
2
7
7
2
6
1
7
7
5
6
6
4
5
2
4
2
7
2
5
5
4
2
5
4
4
7
2
4
2
4
4
4
5
5
6
3
2
4
7
4
2
4
7
7
2
1
2
2
6
2
2
2
5
4
2
2
2
3
5
2
5
3
5
2
3
2
1
2
7
5
5
5
4
7
2
2
4
...

result:

ok 474862 numbers

Test #33:

score: 0
Accepted
time: 424ms
memory: 579888kb

input:

500000
1 2775
1 3338
1 3532
1 3689
1 2814
1 1591
1 3770
1 2339
1 848
1 158
1 1844
1 3903
1 3902
1 1600
1 2346
1 3614
1 57
1 2236
1 1774
1 2145
1 3570
1 3317
1 1681
1 2856
1 1275
1 3020
1 676
1 2294
1 771
1 3264
1 3159
1 2506
1 2173
1 2805
1 1531
1 3494
1 3321
1 1065
1 3651
1 2284
1 3176
1 3743
1 990...

output:

3231
8303
7601
11560
9952
26443
10762
4567
37316
29847
50832
14434
20849
43582
6175
88876
17243
92915
63273
131214
87285
126463
28663
52183
84363
123912
71654
88103
133433
113191
147394
59330
164450
106191
106534
99764
181942
258915
63070
37034
263828
200313
231186
205406
83878
140715
32414
99313
56...

result:

ok 64 numbers

Test #34:

score: 0
Accepted
time: 206ms
memory: 9024kb

input:

500000
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 500000 numbers

Test #35:

score: 0
Accepted
time: 217ms
memory: 9072kb

input:

500000
1 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 10000...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 499999 numbers

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-05 04:43:17 | OpenSource Project