QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#811717#9559. The Towertest_algthAC ✓301ms153652kbC++173.5kb2024-12-12 23:38:472024-12-12 23:38:57

Judging History

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

  • [2024-12-12 23:38:57]
  • 评测
  • 测评结果：AC
  • 用时：301ms
  • 内存：153652kb
查看
  • [2024-12-12 23:38:47]
  • 提交

answer

#include <bits/stdc++.h>

const int MAXN = 5.0001E5;
const int LOG = 25;
const int MAXNODE = MAXN * LOG;
int Ls[MAXNODE], Rs[MAXNODE], fa[MAXNODE], Id[MAXN], Rev[MAXN], A[MAXN], B[MAXN], seg[MAXNODE], rt[MAXN], where[MAXN];
std::array <int, 2> operation[MAXN];
int N, q, top, all, tot, emptyRoot, LIM;
std::unordered_map <int, int> who;

inline int newNode() {
  if (tot + 1 >= MAXNODE) puts("NONONO");
  return ++tot;
}

inline void pushUp(int o) {
  seg[o] = seg[Ls[o]] + seg[Rs[o]];
}

inline void setFa(int a, int b) {
  fa[b] = a;
}

inline void update(int o) {
  pushUp(o);
  setFa(o, Ls[o]), setFa(o, Rs[o]);
}
 
void split(int& o, int& pre, int l, int r, int& lim) {
  if ((!pre) || (!lim)) return ;
  if (l == r) {
    // printf("spl : (%d, %d -> %d) %d\n", l, r, lim, seg[pre]);
    if (lim >= seg[pre]) {
      lim -= seg[pre];
      o = pre, pre = 0;
    } else {
      o = newNode();
      seg[pre] -= lim, seg[o] = lim, lim = 0;
    }
    return ;
  }

  int mid = l + r >> 1;
  o = newNode();
  if (lim >= seg[Ls[pre]]) {
    Ls[o] = Ls[pre], Ls[pre] = 0, lim -= seg[Ls[o]], split(Rs[o], Rs[pre], mid + 1, r, lim);
    // printf("qpls : (%d %d) -> %d\n", l, r, Ls[o]);
  } else {
    split(Ls[o], Ls[pre], l, mid, lim);
  }

  update(o), update(pre);
}

void merge(int& o, int& pre, int l, int r) {  //pre -> emptytree
  if ((!o) || (!pre)) {
    pre += o;//, o = 0;
    // printf("merge : %d, %d %d %d\n", l, r, pre, o);
    return ;
  }

  if (l == r) {
    // printf("merge : %d, %d %d %d\n", l, r, pre, o);
    if (o <= LIM) 
      seg[o] += seg[pre], pre = o, o = 0;
    else
      seg[pre] += seg[o], o = 0; 
    return ;
  }

  int mid = l + r >> 1;
  // printf("sonO : (%d, %d)\n", Ls[o], Rs[o]);
  // printf("sonPre : (%d, %d)\n", Ls[pre], Rs[pre]);
  merge(Ls[o], Ls[pre], l, mid), merge(Rs[o], Rs[pre], mid + 1, r), o = 0;
  update(pre);
}

void build(int& o, int l, int r) {
  o = newNode();
  if (l == r) {
    seg[o] = A[l] - A[l - 1];
    where[l] = o;
    return ;
  }
  int mid = l + r >> 1;
  build(Ls[o], l, mid), build(Rs[o], mid + 1, r);
  update(o);
}

int main() {
  // freopen("A.in", "r", stdin);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  std::cin >> q;
  for (int i = 1, a, b; i <= q; ++i) {
    std::cin >> a >> b;
    operation[i] = {a, b};
    if (a == 1) {
      Rev[Id[i] = ++all] = i;
    }
      
    if (a == 3) {
      A[++N] = b;
    }
  }

  if (N == 0) {
    return 0;
  }

  std::sort(A + 1, A + 1 + N);
  top = std::unique(A + 1, A + 1 + N) - A - 1;
  // std::cerr << top << '\n'; 

  build(emptyRoot, 1, top);
  LIM = tot;
  for (int i = 1; i <= q; ++i) {
    auto [a, b] = operation[i];
    int nowId = Id[i];
    if (a == 1) {
      split(rt[nowId], emptyRoot, 1, top, b);
      who[rt[nowId]] = nowId;
      // printf("(%d, %d) -> %d\n", i, nowId, rt[nowId]);
      // std::cout << "rt : " << rt[nowId] << '\n';
    }

    if (a == 2) {
      nowId = b;
      merge(rt[nowId], emptyRoot, 1, top);
      // printf("empr : %d nowId : %d\n", emptyRoot, nowId);
      who[emptyRoot] = 0;
    }

    if (a == 3) {
      b = std::lower_bound(A + 1, A + 1 + top, b) - A;
      // std::cout << b << '\n';
      int curNode = where[b];
      while (fa[curNode] != 0) {
        curNode = fa[curNode];
      }

      std::cout << who[curNode] << '\n';
      // printf("ans : (%d, %d)\n", curNode, who[curNode]);
    }
  }

  return 0;
}
Source code, Language: C++17

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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

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: 220ms
memory: 72852kb

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: 208ms
memory: 82240kb

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: 178ms
memory: 79548kb

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: 44ms
memory: 13856kb

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: 202ms
memory: 153652kb

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: 301ms
memory: 100064kb

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: 151ms
memory: 97108kb

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: 296ms
memory: 114344kb

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: 234ms
memory: 40544kb

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: 160ms
memory: 87580kb

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: 264ms
memory: 42824kb

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: 2ms
memory: 15936kb

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

input:

1
3 11451419

output:

0

result:

ok 1 number(s): "0"

Test #20:

score: 0
Accepted
time: 161ms
memory: 68940kb

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: 47ms
memory: 37672kb

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: 256ms
memory: 81656kb

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: 157ms
memory: 89288kb

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: 72ms
memory: 76888kb

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: 59ms
memory: 54340kb

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: 166ms
memory: 93996kb

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: 175ms
memory: 91124kb

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: 215ms
memory: 98576kb

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: 144ms
memory: 108684kb

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: 213ms
memory: 39796kb

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: 254ms
memory: 42920kb

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: 263ms
memory: 45600kb

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: 72ms
memory: 96076kb

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: 47ms
memory: 14568kb

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: 70ms
memory: 19512kb

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: 2025-01-20 22:36:53 | OpenSource Project