QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#791748#9559. The Towergrass8cowAC ✓805ms84304kbC++172.8kb2024-11-28 20:40:412024-11-28 20:40:45

Judging History

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

  • [2024-11-28 20:40:45]
  • 评测
  • 测评结果：AC
  • 用时：805ms
  • 内存：84304kb
查看
  • [2024-11-28 20:40:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define ll long long
#define fi first
#define se second
int f[N],ch[N][2];
int b[N],mx[N];
#define pi pair<ll,ll>
pi a[N],mi[N];
ll tag[N];
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define isroot(x) (ls(f[x])!=x&&rs(f[x])!=x)
#define op(x) (ch[f[x]][1]==x)
void ad(int x,ll z){a[x].fi+=z,mi[x].fi+=z,tag[x]+=z;}
void up(int x){
    int l=ls(x),r=rs(x);
    mi[x]=a[x],mx[x]=max(b[x],max(mx[r],mx[l]));
    if(l)mi[x]=min(mi[x],mi[l]);
    if(r)mi[x]=min(mi[x],mi[r]);
}
void pd(int x){
    if(tag[x])ad(ls(x),tag[x]),ad(rs(x),tag[x]),tag[x]=0;
}
void rot(int x){
	int y=f[x],z=f[y];
	if(!isroot(y))ch[z][op(y)]=x;
	int k=op(x),v=ch[x][!k];
	ch[x][!k]=y,ch[y][k]=v;
	f[v]=y,f[y]=x,f[x]=z;
	up(y),up(x);
}
void upd(int x){
	if(!isroot(x))upd(f[x]);
	pd(x);
}
void splay(int x){
	upd(x); 
	while(!isroot(x)){
		if(!isroot(f[x]))rot((op(x)^op(f[x]))?x:f[x]);
		rot(x);
	}
}
void access(int x){for(int p=0;x;p=x,x=f[x])splay(x),rs(x)=p,up(x);}
int f_[N];
void lin(int u,int v){splay(u),f[u]=v,f_[u]=v;}
void cut(int u,int v){
	access(u),splay(u),splay(v);
	f[u]=rs(v)=0,up(v);
}
const ll V=1e18;
int R[N],n,wh[N],m,T,bh[N],hb[N];
ll ans[N];
void Ask(int x){
    access(1),splay(1);int u=1,nx=1;
    int me=0;
    while(u){
        nx=u;
        if(rs(u)&&x<mx[rs(u)])u=rs(u);
        else{
            me=max(me,mx[rs(u)]);
            if(x>=b[u])me=max(me,b[u]);
            u=ls(u);
        }
    }
    splay(nx);
    if(f_[me]==me+1)ans[x]=-1;
    else ans[x]=f_[me];
}
int main(){
	scanf("%d",&n);T=n+1;
    for(int i=1;i<=n+1;i++)a[i]=mi[i]={V,i},b[i]=mx[i]=i;
    vector<pair<ll,int> >Q;
    int fuc=0;
	for(int i=1,op;i<=n;i++){
        ll x;
        scanf("%d%lld",&op,&x);
        if(op==1){
            fuc++;
            T++,a[T]=mi[T]={x,T},bh[i]=T;
            R[i]=n+1,wh[T]=i;
        }
        if(op==2)R[wh[x+n+1]]=i+1;
        if(op==3) Q.push_back({x,i});
    }
    for(int i=1;i<=n;i++){
        if(R[i])lin(i,bh[i]),lin(bh[i],R[i]),hb[bh[i]]=i;
        else lin(i,i+1);
    }
    sort(Q.begin(),Q.end());reverse(Q.begin(),Q.end());
    int doi=0;ll S=0;
    while(doi<fuc&&!Q.empty()){
        access(1);splay(1);ll E=mi[1].fi;
        ad(1,-E);
        while(!Q.empty()&&Q.back().fi<=S+E)
        Ask(Q.back().se),Q.pop_back();
        while(mi[1].fi==0){
            doi++;
            int e=mi[1].se;
            cut(hb[e],e),cut(e,R[hb[e]]);
            lin(hb[e],hb[e]+1);
            access(1),splay(1);
        }
        S+=E;
    }
    while(!Q.empty())Ask(Q.back().se),Q.pop_back();
    for(int i=1;i<=n;i++)
        if(ans[i]!=0){
            if(ans[i]>0)ans[i]-=(n+1);
            else ans[i]=0;
            printf("%d\n",ans[i]);
        }
	return 0;
}
源文件, 语言: C++17

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

詳細信息

Test #1:

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

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

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: 3ms
memory: 22548kb

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

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

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

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: 805ms
memory: 76844kb

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: 319ms
memory: 75284kb

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: 203ms
memory: 78476kb

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

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: 183ms
memory: 84304kb

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: 485ms
memory: 75772kb

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: 81ms
memory: 70352kb

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: 225ms
memory: 78908kb

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: 149ms
memory: 72640kb

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: 773ms
memory: 75660kb

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: 405ms
memory: 72188kb

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

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

input:

1
3 11451419

output:

0

result:

ok 1 number(s): "0"

Test #20:

score: 0
Accepted
time: 265ms
memory: 76432kb

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: 125ms
memory: 74036kb

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: 717ms
memory: 79988kb

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: 685ms
memory: 82204kb

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: 209ms
memory: 80816kb

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: 107ms
memory: 80940kb

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: 411ms
memory: 79924kb

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: 514ms
memory: 75664kb

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: 375ms
memory: 82548kb

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: 252ms
memory: 83112kb

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: 156ms
memory: 70188kb

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: 146ms
memory: 71072kb

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: 147ms
memory: 72188kb

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: 138ms
memory: 83100kb

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: 153ms
memory: 64920kb

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: 117ms
memory: 59920kb

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 繁體中文 简体中文

伺服器時間: 2024-12-13 00:12:19 | 開源專案