QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#774074#9559. The TowerYoralenAC ✓648ms173108kbC++142.0kb2024-11-23 11:35:322024-11-23 11:35:38

Judging History

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

  • [2024-11-23 11:35:38]
  • 评测
  • 测评结果：AC
  • 用时：648ms
  • 内存：173108kb
查看
  • [2024-11-23 11:35:32]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N=1000005,Lim=1e9;
struct Tree{
	int ls,rs,num,fa;
	void cl(){ls=rs=num=fa=0;}
}t[N*40];
struct Que{int op,x;}a[N];
struct Rg{int l,r;}rg[N];
int tot=1,st[N],rt[N],P,n,m,cl[N*40],tid[N*40];
map<int,int>I;
void Split(int &p,int q,int l,int r,int siz){
	if(!siz)return;p=++tot;
	if(t[q].num<=siz){
		t[p]=t[q];t[q].cl();
		t[t[p].ls].fa=t[t[p].rs].fa=p;return;
	}
	int mid((l+r)>>1);
	t[p].num+=siz,t[q].num-=siz;
	if(l==r){return;}
	int val=t[t[q].ls].num;
	if(val>siz)Split(t[p].ls,t[q].ls,l,mid,siz);
	else{
		t[p].ls=t[q].ls;t[q].ls=0;t[t[p].ls].fa=p;
		Split(t[p].rs,t[q].rs,mid+1,r,siz-val);
	}
	t[p].num=t[t[p].ls].num+t[t[p].rs].num;
	t[t[p].ls].fa=t[t[p].rs].fa=p;
}
int Mg(int u,int v,int l,int r){
	if(!u||!v)return u+v;
	if(l==r){t[u].num+=t[v].num;return u;}
	int mid((l+r)>>1);
	t[u].ls=Mg(t[u].ls,t[v].ls,l,mid);
	t[u].rs=Mg(t[u].rs,t[v].rs,mid+1,r);
	t[t[u].ls].fa=t[t[u].rs].fa=u;
	t[u].num=t[t[u].ls].num+t[t[u].rs].num;
	return u;
}
void Build(int &x,int l,int r){
	x=++tot;int mid((l+r)>>1);
	if(l==r){t[x].num=rg[l].r-rg[l].l+1;tid[l]=x;return;}
	Build(t[x].ls,l,mid);Build(t[x].rs,mid+1,r);
	t[x].num=t[t[x].ls].num+t[t[x].rs].num;
	t[t[x].ls].fa=t[t[x].rs].fa=x;
}
int main(){
	int i,tp=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&a[i].op,&a[i].x);
		if(a[i].op==3){st[++tp]=a[i].x;}
	}
	sort(st+1,st+1+tp);
	tp=unique(st+1,st+1+tp)-st-1;
//	printf("!%d\n",tp);
	for(i=1;i<=tp;i++){
		if(st[i-1]+1<=st[i]-1)rg[++m]=(Rg){st[i-1]+1,st[i]-1};
		rg[++m]=(Rg){st[i],st[i]};I[st[i]]=m;
	}
	if(st[tp]+1<=Lim)rg[++m]=(Rg){st[tp]+1,Lim};
//	for(i=1;i<=m;i++)printf("~%d %d\n",rg[i].l,rg[i].r);
	
	Build(rt[0],1,m);
	
	for(i=1;i<=n;i++){
		if(a[i].op==1)P++,Split(rt[P],rt[0],1,m,a[i].x),cl[rt[P]]=P;
		if(a[i].op==2)cl[rt[a[i].x]]=0,Mg(rt[0],rt[a[i].x],1,m);
		if(a[i].op==3){
			int p=tid[I[a[i].x]];
			while(t[p].fa)p=t[p].fa;
			printf("%d\n",cl[p]);
		}
	}
}
Source code, Language: C++14

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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

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: 226ms
memory: 89428kb

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: 214ms
memory: 55656kb

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: 191ms
memory: 49416kb

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: 49ms
memory: 28312kb

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: 118ms
memory: 173108kb

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: 180ms
memory: 117244kb

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: 90ms
memory: 33228kb

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: 337ms
memory: 145732kb

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: 580ms
memory: 86184kb

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: 108ms
memory: 98500kb

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: 648ms
memory: 86916kb

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

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

input:

1
3 11451419

output:

0

result:

ok 1 number(s): "0"

Test #20:

score: 0
Accepted
time: 94ms
memory: 68528kb

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: 49ms
memory: 30496kb

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: 347ms
memory: 105404kb

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: 126ms
memory: 96456kb

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: 63ms
memory: 75496kb

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: 56ms
memory: 50984kb

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: 169ms
memory: 108924kb

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: 199ms
memory: 107524kb

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: 173ms
memory: 110180kb

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: 115ms
memory: 117524kb

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: 576ms
memory: 87292kb

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: 580ms
memory: 91408kb

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: 578ms
memory: 92680kb

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: 55ms
memory: 102172kb

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: 60ms
memory: 18128kb

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: 77ms
memory: 22308kb

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-12 11:46:29 | OpenSource Project