QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#645074#7626. Quake and RebuildDisplace_TL 2397ms10412kbC++143.2kb2024-10-16 16:47:562024-10-16 16:47:58

Judging History

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

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2024-10-16 16:47:58]
  • 评测
  • 测评结果:TL
  • 用时:2397ms
  • 内存:10412kb
  • [2024-10-16 16:47:56]
  • 提交

answer

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int N=2e5+5;
const int B=300;
int n, m;
int lp[N], rp[N], bid[N];
int fa[N], nxt[N], dis[N];
int ins[N];
int dt[N];
inline void rebuild(int i){
	if(dt[i]>=B) return ;
	for(int j=lp[i]; j<=rp[i]; ++j){
		int x=j; dis[j]=0;
		while(x>=lp[i]) ++dis[j], x=max(1, fa[x]-dt[i]);
		nxt[j]=x;
	}
}
#define gf(x) (dt[bid[x]]<B?nxt[x]:max(1, fa[x]-dt[bid[x]]))
inline int lca(int x, int y){
	while(gf(x)^gf(y)){
		if(x<y) y=gf(y);
		else x=gf(x);
	}
	if(bid[x]!=bid[y]) return gf(x);
	while(x^y){
		if(x<y) y=max(1, fa[y]-dt[bid[y]]);
		else x=max(1, fa[x]-dt[bid[x]]);
	}
	return x;
}
inline int dep(int x){
	int ret=0;
	while(x^1){
		if(dt[bid[x]]<B) ret+=dis[x], x=nxt[x];
		else ++ret, x=max(1, fa[x]-dt[bid[x]]);
	}
	return ret;
}
inline int getd(int x, int y){
	if(x==y) return 0;
	return dep(x)+dep(y)-2*dep(lca(x, y));
}
inline int jump(int x, int t){
	while(gf(x)>t) x=gf(x);
	while(max(1, fa[x]-dt[bid[x]])>t) x=max(1, fa[x]-dt[bid[x]]);
	return x;
}
inline bool cmp(int x, int y){
	if(x==y)  return false;
	int t=lca(x, y);
	if(t==x) return true;
	if(t==y) return false;
	return jump(x, t)<jump(y, t);
}
int vec[N], vec2[N], sz, p1, p2, it;
inline void work(int l, int r){
	if(l==r) return ;
	int mid=(l+r)>>1;
	work(l, mid); work(mid+1, r);
	p1=l; p2=mid+1; it=l; 
	while(p1<=mid||p2<=r){
		if(p1>mid){
			vec2[it++]=vec[p2++];
		}
		else if(p2>r){
			vec2[it++]=vec[p1++];
		}
		else{
			if(cmp(vec[p1], vec[p2])) vec2[it++]=vec[p1++];
			else vec2[it++]=vec[p2++];
		}
	}
	for(int i=l; i<=r; ++i) vec[i]=vec2[i];
}
int main(){
	// freopen("D:\\nya\\acm\\B\\test.in","r",stdin);
	// freopen("D:\\nya\\acm\\B\\test.out","w",stdout);
	read(n); read(m);
	for(int i=2; i<=n; ++i) read(fa[i]);
	for(int i=2; i<=n; ++i) bid[i]=(i-2)/B+1;
	bid[1]=0; 
	lp[0]=rp[0]=1; dt[0]=B;
	for(int i=1; i<=bid[n]; ++i) lp[i]=rp[i-1]+1, rp[i]=rp[i-1]+B;
	rp[bid[n]]=n;
	for(int i=1; i<=bid[n]; ++i) rebuild(i);
	while(m--){
		int op; read(op);
		if(op==1){
			int l, r, d; read(l); read(r); read(d);
			if(bid[l]==bid[r]){
				for(int i=l; i<=r; ++i) fa[i]-=d;
				rebuild(bid[l]);
				continue;
			}
			for(int i=l; i<=rp[bid[l]]; ++i) fa[i]-=d;
			rebuild(bid[l]);
			for(int i=lp[bid[r]]; i<=r; ++i) fa[i]-=d;
			rebuild(bid[r]);
			for(int i=bid[l]+1; i<bid[r]; ++i){
				dt[i]+=d; dt[i]=min(dt[i], n); rebuild(i);
			}
		}
		else{
			int k, x; 
			read(k); 
			if(k==0){
				printf("0\n");
				continue;
			}
			sz=0;
			while(k--){
				read(x); if(!ins[x]) vec[++sz]=x, ins[x]=1;
			}
			work(1, sz);
			vec[0]=vec[sz];
			int ans=0;
			for(int i=1; i<=sz; ++i) ans+=getd(vec[i-1], vec[i]), ins[vec[i]]=0;
			ans>>=1;
			printf("%d\n", ans+1);
		}
	}
	return 0;
}

詳細信息

Test #1:

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

input:

4 5
1 2 2
2 2 1 4
1 2 3 1
2 3 2 3 4
1 4 4 1
2 2 3 4

output:

3
4
3

result:

ok 3 lines

Test #2:

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

input:

10 10
1 2 3 3 4 5 7 7 9
1 2 10 3
2 9 9 5 3 10 7 2 4 6 8
1 6 10 3
1 2 7 3
1 7 10 3
2 2 4 3
2 3 7 4 4
1 3 9 3
1 3 9 3
1 10 10 3

output:

10
3
3

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 87ms
memory: 10012kb

input:

3051 198219
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...

output:

78
78
70
64
60
55
60
58
52
54
51
53
56
51
51
57
55
52
49
55
49
50
53
49
49
48
49
48
53
50
50
54
47
52
45
49
49
46
47
48
49
50
48
49
47
48
47
49
48
50
48
49
48
47
49
48
51
48
48
45
45
46
50
50
50
48
49
46
47
47
46
48
48
47
49
47
46
47
46
47
46
45
47
49
49
50
51
48
48
49
47
47
48
50
46
47
48
50
46
47
...

result:

ok 13214 lines

Test #4:

score: 0
Accepted
time: 122ms
memory: 9988kb

input:

6173 198631
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

2819
1049
1155
831
722
5962
123
624
554
601
241
597
81
29
34
390
350
443
385
6038
6083
258
5
315
27
281
6029
300
6136
322
227
46
271
263
26
268
257
6101
5816
255
258
156
243
270
186
6099
16
13
5435
163
7
35
219
182
214
10
24
23
194
178
188
183
200
167
158
197
24
189
131
35
167
24
189
15
183
176
6050...

result:

ok 30261 lines

Test #5:

score: 0
Accepted
time: 58ms
memory: 9924kb

input:

9724 198809
1 1 1 1 1 1 1 1 1 4 2 2 1 2 1 4 1 5 1 3 4 2 2 4 2 7 4 1 2 6 9 2 1 1 2 3 1 1 3 4 3 1 2 1 18 1 3 4 2 4 4 6 1 4 2 1 7 11 4 1 5 6 2 12 3 4 4 7 1 1 11 4 15 21 3 4 15 1 1 12 11 3 1 1 16 9 14 2 5 9 3 5 9 3 8 5 15 16 9 14 13 8 2 4 5 10 6 1 10 11 10 12 7 4 36 6 5 7 6 13 7 1 14 5 1 6 8 7 1 10 20 6...

output:

24
25
31
31
27
25
29
23
23
21
26
23
21
24
23
23
26
26
21
24
27
23
23
23
20
19
20
18
28
25
26
21
19
21
21
26
20
23
17
20
18
21
22
22
18
21
25
18
17
18
24
18
16
18
19
24
20
18
19
17
17
21
25
19
21
23
19
23
15
17
19
19
22
18
20
18
21
19
18
18
15
16
22
17
17
18
13
16
19
16
15
16
18
16
15
17
15
18
18
20
...

result:

ok 66269 lines

Test #6:

score: 0
Accepted
time: 520ms
memory: 9916kb

input:

12796 185791
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

12100
7532
12357
12774
211
12761
5309
1646
12726
1882
247
118
1660
12229
12143
1499
1368
1273
1387
341
274
1374
1237
1359
112
1152
981
12681
949
890
820
774
62
644
836
925
12
13
1203
666
732
731
1127
12320
11473
82
655
12788
569
5866
621
2798
12114
85
609
11827
1
12455
56
605
575
530
54
645
1845
93
...

result:

ok 3210 lines

Test #7:

score: 0
Accepted
time: 107ms
memory: 9888kb

input:

16122 194030
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

9730
7096
4371
4171
3732
3716
3273
2910
2530
2423
2366
2351
2013
2196
2430
1891
1833
1852
1638
1709
1762
1699
1423
1295
1471
1255
1356
1428
1214
1191
1066
1104
1131
1116
1010
860
964
949
927
994
879
829
718
787
786
754
757
795
820
739
761
689
659
658
587
663
654
658
631
593
633
583
575
598
554
579
4...

result:

ok 9701 lines

Test #8:

score: 0
Accepted
time: 124ms
memory: 9980kb

input:

19492 191214
1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3 1 2 10 10 1 2 2 1 1 1 1 2 1 2 2 4 3 1 1 4 10 2 5 6 1 1 6 11 3 7 1 6 5 4 8 8 12 2 4 5 6 1 2 4 10 4 8 15 3 1 15 1 1 4 9 6 9 2 2 11 3 6 11 17 6 6 2 5 10 8 3 3 4 2 1 3 3 12 1 14 1 1 6 1 5 7 23 7 12 8 13 1 11 13 6 22 3 20 2 8 4 1 41 5 3 27 13 15 4 4 6 9 ...

output:

207
284
264
237
41
207
17559
198
186
201
168
1
1461
9
218
170
156
191
7
195
189
177
165
18623
170
25
151
18433
168
181
164
179
188
18572
1
171
172
182
137
179
184
127
162
166
167
171
17
147
180
165
175
173
167
1359
20
161
138
175
169
176
178
6
152
178
7
121
16
12
4
9
8
5
4
6
29
6
7
10
42
5
3
1
5
27
...

result:

ok 18556 lines

Test #9:

score: 0
Accepted
time: 73ms
memory: 9912kb

input:

22808 195820
1 1 1 1 1 1 1 1 1 1 2 2 1 1 2 2 1 1 3 2 1 2 4 4 1 2 1 5 4 1 4 2 1 3 1 1 3 1 4 3 4 5 15 1 6 10 1 1 3 1 1 1 1 3 5 7 4 2 3 15 4 4 1 11 1 2 5 2 2 12 4 3 1 9 6 4 2 1 3 5 5 1 4 1 2 16 15 1 6 1 10 1 9 6 9 2 1 12 6 2 13 2 3 1 8 17 2 8 1 16 5 28 4 24 2 9 5 1 11 18 15 6 7 10 3 1 1 11 8 1 12 4 7 1...

output:

42
45
42
45
40
47
43
37
38
41
37
44
42
38
42
34
34
32
37
37
37
39
35
45
35
40
32
36
43
34
33
39
29
32
33
33
33
31
28
32
35
31
23
33
31
30
26
34
28
30
35
32
32
30
33
28
26
29
30
26
24
27
25
28
22
30
26
27
23
29
31
25
27
30
26
26
33
30
27
26
21
32
27
28
28
25
31
26
24
24
24
23
30
22
26
21
26
27
24
22
...

result:

ok 39164 lines

Test #10:

score: 0
Accepted
time: 146ms
memory: 10176kb

input:

26352 183295
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 1 1 1 2 2 1 1 1 2 11 1 2 1 4 1 2 3 1 3 3 4 2 3 2 5 3 2 1 2 1 3 6 1 2 3 1 6 3 2 4 3 1 7 3 6 3 10 1 1 2 5 1 1 7 3 2 3 3 8 7 2 5 9 2 3 1 9 3 1 2 8 7 5 1 2 1 1 11 5 2 3 8 3 7 4 1 6 5 1 10 16 11 3 4 3 6 14 4 3 15 27 14 2 3 5 6 14 15 11 21 2 3 2 1...

output:

25212
25
316
497
330
4
314
304
24633
297
285
5
252
26284
11
256
281
275
26265
12
1
14
17
12
6
12
5
10
3
15
9
7
10
1
1
9
9
3
40
11
10
19
9
9
9
14
4
17
3
8
13
5
6
9
32
12
6
4
6
3
4
4
1
4
1991
29
40
1
5
30
911
3
9
11
44
45
3
1
15
1
16
9
16
14
3
15
31
15
1
7
14
367
3479
5
4
14
6
25
13
4
7
3
5
14
18
8
13...

result:

ok 3811 lines

Test #11:

score: 0
Accepted
time: 80ms
memory: 9892kb

input:

27196 199560
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 3 2 4 1 1 2 4 1 2 1 2 5 3 5 4 1 1 2 4 1 2 11 4 2 7 1 1 3 1 1 2 2 5 2 2 6 1 3 3 2 4 7 2 5 3 2 6 10 4 2 6 3 2 1 2 2 17 1 1 2 5 9 5 4 19 12 2 12 3 2 19 4 4 12 7 6 5 9 3 2 6 3 13 1 1 11 9 6 14 9 3 3 4 17 6 1 5 13 3 1 32 15 26 3 1 2 15 3 1 4 14 2 7 2 1...

output:

82
78
77
73
75
72
69
68
65
65
63
59
65
60
65
71
58
67
64
64
62
61
62
67
46
61
54
60
56
55
51
52
45
47
54
51
49
45
53
45
53
46
43
41
42
51
48
48
43
40
44
45
42
47
43
40
42
51
44
44
42
44
43
39
43
42
40
41
44
41
39
41
39
42
36
41
42
38
42
38
42
42
44
40
44
45
35
37
38
38
40
37
38
42
42
41
35
40
39
37
...

result:

ok 19956 lines

Test #12:

score: 0
Accepted
time: 1079ms
memory: 10228kb

input:

32698 192710
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

32631
1529
1
1074
3158
151
32359
5093
4935
1295
32642
3805
365
3196
3342
2990
3159
3152
30578
509
2975
3034
32641
2753
7381
8616
2802
2351
32349
358
101
385
1998
8785
1
1959
5152
1923
1899
1763
395
1800
31873
1708
1729
185
1678
1507
1740
1591
1498
1633
102
1461
32109
1355
591
32295
1441
32692
146
53...

result:

ok 246 lines

Test #13:

score: 0
Accepted
time: 85ms
memory: 10076kb

input:

35920 186806
1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 4 1 4 3 2 1 1 4 3 2 5 2 1 2 2 3 8 5 1 1 9 1 6 8 1 3 4 4 8 2 8 4 11 4 4 3 1 15 8 3 9 8 1 2 3 4 4 4 2 3 3 1 3 1 6 11 8 3 9 4 4 11 13 6 2 2 10 9 10 1 1 1 15 4 1 7 5 5 2 8 20 16 2 15 1 8 5 2 6 4 3 13 11 3 3 4 1 16 1 2 7 2 4 18 12 3 4 4 37 7 12 21 2 27 15 ...

output:

109
105
104
101
102
97
103
99
93
96
99
100
88
87
90
90
84
88
96
78
95
85
88
86
91
86
77
87
80
88
80
75
76
81
73
76
82
81
81
76
78
72
82
72
80
66
66
75
68
61
81
75
69
72
74
66
71
60
60
70
59
71
67
59
69
60
54
67
57
60
59
64
68
69
58
56
60
52
58
66
56
62
63
56
56
62
56
62
52
58
58
51
49
62
51
58
54
53...

result:

ok 15567 lines

Test #14:

score: 0
Accepted
time: 268ms
memory: 10228kb

input:

39372 196317
1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 3 1 3 2 2 1 1 1 4 4 3 6 1 2 1 5 4 7 2 5 1 2 2 5 2 12 2 7 7 2 5 6 14 2 5 4 6 2 8 14 2 3 4 8 12 1 2 5 3 1 10 6 8 3 4 4 8 13 2 2 6 14 12 4 3 29 8 2 1 39 2 15 9 17 1 7 18 1 5 2 9 6 7 1 6 10 3 14 10 35 12 4 17 2 2 3 11 6 7 2 6 12 12 9 9 6 4 22 5 7 5 26 5 5...

output:

36323
444
26954
457
83
38918
85
36668
383
362
1535
35763
51
339
301
38085
49
327
291
269
34799
278
34
11
31977
297
297
261
288
38187
42
286
37406
11131
293
1495
288
38036
268
8
627
235
3191
245
232
37103
272
264
23
34
271
2433
242
269
86
263
5
239
214
4
241
230
233
34576
237
34789
260
232
36453
3710...

result:

ok 76 lines

Test #15:

score: 0
Accepted
time: 67ms
memory: 7920kb

input:

32241 199734
1 1 1 1 2 2 2 1 1 2 1 1 1 3 2 2 1 1 2 1 1 2 1 3 2 1 1 4 1 1 6 3 1 1 1 6 1 9 7 5 2 1 7 2 4 1 1 5 5 3 3 5 5 5 1 1 1 2 2 2 2 9 7 3 7 7 10 3 6 4 4 3 2 4 5 1 3 1 4 6 1 15 1 1 1 2 17 8 12 3 2 3 6 9 7 5 1 3 12 17 2 5 15 2 3 3 12 7 4 35 8 9 5 4 18 5 10 8 26 13 2 2 1 15 6 2 3 1 19 2 8 8 3 11 13 ...

output:

34
31
29
34
26
32
28
24
31
31
32
30
29
28
26
29
27
24
26
28
32
30
31
23
28
28
25
32
22
23
27
28
29
29
31
29
27
27
31
26
32
26
27
28
28
28
24
23
29
25
21
22
22
26
27
24
25
27
23
22
26
22
21
23
26
23
23
24
22
19
28
22
25
19
23
20
27
24
24
22
24
26
21
21
23
23
20
25
21
27
21
21
26
22
22
21
22
23
24
29
...

result:

ok 66578 lines

Test #16:

score: 0
Accepted
time: 189ms
memory: 10252kb

input:

44885 197554
1 1 1 1 1 1 1 1 1 1 1 3 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 6 1 5 7 3 4 3 3 2 4 2 2 2 3 2 4 2 1 2 1 2 1 10 2 1 17 1 4 1 9 1 19 2 14 4 2 3 8 3 2 3 2 2 6 1 1 6 13 8 4 2 7 13 1 19 1 21 9 6 3 2 1 5 5 1 6 1 1 4 14 2 18 5 11 3 6 5 2 6 2 2 19 9 8 14 2 5 9 18 11 10 1 6 7 12 8 14 7 6 20 1 1 4 14...

output:

128
476
30
93
44813
104
463
420
421
422
7
399
430
369
404
5669
407
6
23
373
394
5
43609
363
379
31
375
9
319
1
342
350
285
16
31
357
330
321
338
309
316
30
71
327
335
69
227
300
33
334
330
323
333
26
50
50
285
6
14
302
5
1
25
7
285
35
310
19
23
256
10
41447
274
326
260
317
311
22
304
12
319
35
283
3...

result:

ok 507 lines

Test #17:

score: 0
Accepted
time: 76ms
memory: 7892kb

input:

47487 188796
1 1 1 1 1 1 1 1 2 1 2 2 2 2 1 1 1 3 2 3 2 2 2 1 2 8 4 2 4 1 1 7 6 3 3 6 5 2 1 1 1 8 5 1 2 3 7 1 3 5 4 6 1 7 6 4 7 5 4 7 9 10 7 7 10 6 7 6 24 1 4 3 11 7 1 7 3 1 1 2 4 10 5 6 16 3 18 3 6 3 4 2 1 3 10 22 11 14 8 8 3 28 3 5 5 6 4 27 4 1 5 3 14 15 15 20 27 5 7 25 2 25 6 2 5 2 14 16 2 5 20 11...

output:

12
13
13
12
12
13
12
13
14
13
13
11
12
11
12
12
13
15
14
14
12
11
13
13
13
11
10
13
12
13
10
10
12
11
13
12
14
11
10
11
14
10
11
14
10
8
13
11
12
10
12
13
13
13
13
12
12
11
14
12
14
13
10
12
12
13
13
11
14
13
11
12
9
11
12
13
10
10
11
11
11
11
12
12
11
11
13
11
11
12
12
12
13
13
14
11
12
10
11
11
11...

result:

ok 188796 lines

Test #18:

score: 0
Accepted
time: 195ms
memory: 8368kb

input:

50332 196622
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 2 3 1 5 3 1 3 1 1 2 6 2 1 2 2 6 1 1 2 1 2 2 2 1 2 3 6 4 2 3 1 1 1 1 1 1 3 10 3 6 7 3 4 12 2 4 17 2 9 14 7 1 5 5 1 3 1 2 1 5 8 3 3 2 1 1 7 3 2 1 20 1 3 5 1 9 5 7 1 1 1 26 20 16 5 7 9 3 1 13 8 4 4 26 8 4 5 1 2 5 1 1 6 21 7 4 1 12 9 6 8 6 11 4 12 4...

output:

519
482
447
482
405
21
5
412
19
393
5
396
46280
406
356
377
11
353
323
389
334
367
373
324
360
355
34
6
336
5
1
349
349
329
331
290
353
11
344
59
315
50161
330
336
296
318
314
320
306
321
9
19
12
324
318
5
329
9
293
4
291
332
4
303
6
4
309
304
320
16
13
289
305
301
324
311
12
300
311
296
1
278
44
23...

result:

ok 604 lines

Test #19:

score: 0
Accepted
time: 69ms
memory: 9888kb

input:

56089 161372
1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 2 1 1 3 1 2 1 4 2 2 1 3 2 2 1 2 2 2 2 1 2 1 3 1 2 7 5 2 6 2 1 7 3 2 1 2 4 3 4 7 5 3 1 1 1 7 2 3 3 5 1 4 1 2 1 3 2 7 1 1 5 3 2 1 6 2 2 3 4 1 8 6 10 20 1 10 6 6 6 5 1 12 7 11 1 1 1 2 1 3 4 4 5 12 1 1 3 3 9 6 3 14 1 8 7 6 16 12 4 2 3 3 6 1 5 1 1 4 17 3 5 1...

output:

47
45
43
45
43
44
33
42
37
43
39
37
36
39
42
35
41
40
41
37
41
35
35
34
35
46
36
40
37
39
36
39
33
40
34
33
37
42
41
33
34
33
36
34
34
33
38
37
32
36
34
32
28
34
30
37
34
34
32
32
30
31
33
27
31
30
38
34
28
40
26
36
32
33
28
30
32
34
28
27
33
31
26
29
36
33
27
27
31
28
27
36
29
30
28
32
32
26
32
31
...

result:

ok 32274 lines

Test #20:

score: 0
Accepted
time: 290ms
memory: 10196kb

input:

57560 196345
1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 3 1 1 1 1 1 1 1 1 2 1 4 1 2 2 1 1 3 1 1 1 3 1 1 2 2 6 1 3 5 3 1 1 6 5 5 1 4 1 1 8 1 2 5 2 5 5 1 3 2 6 5 3 18 4 2 1 1 6 15 3 2 8 6 6 2 7 4 7 3 1 5 6 2 2 4 8 2 1 2 3 4 2 12 4 1 1 6 1 6 1 15 3 5 2 2 7 12 2 9 3 5 1 1 3 7 27 20 15 2 12 5 13 1 2 2 21 6 5 6 5 10...

output:

482
522
56984
52319
54021
484
455
449
420
412
56447
417
62
6
49729
57292
4155
44
55140
6021
57280
8733
56276
381
56520
368
370
350
356
13
6892
278
360
31835

result:

ok 34 lines

Test #21:

score: 0
Accepted
time: 198ms
memory: 9944kb

input:

62897 169366
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

34539
26796
22337
18729
14048
12335
10923
11935
8735
8550
7231
7803
8416
7263
6405
7104
7138
6337
6647
5576
5926
5746
4990
4960
5242
4885
5122
4662
5107
4790
4742
4662
4737
4392
4324
4228
4411
3844
3821
4054
3828
3729
3535
3360
3183
3263
3427
3349
3298
3158
2518
2960
2921
3055
2689
2724
2706
2646
24...

result:

ok 9962 lines

Test #22:

score: 0
Accepted
time: 159ms
memory: 10188kb

input:

60682 186488
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 3 2 1 1 1 4 4 1 2 1 1 1 1 2 4 7 1 1 11 1 5 3 1 2 1 1 1 1 3 3 1 1 4 2 1 2 4 2 6 4 5 2 3 15 3 3 1 3 11 3 12 4 11 6 4 4 4 1 2 1 5 2 6 6 1 2 19 3 6 3 7 1 3 2 2 2 4 14 1 3 1 1 1 8 5 2 4 2 4 11 4 3 1 1 11 8 8 1 2 6 8 2 4 5 8 3 4 12 17 11 14 2 10 1 3 5 14 ...

output:

22
493
25
497
36
40
57595
16
12
1
3
9
1
8
16
39
11
28
4
16
14
21
1
3
1
4
30
236
3
1
26
40
3
15
3
11
3
45
9
3
1
14
3
242
1
1
198
7
25
4
4
10
226
27
3
11
243
6
54515
7
243
25
19
4
21
6
241
14
13
4
26
28
5
13
36
20
15
12
7
3
19
4
13
22
31
70
221
3
11
4
15
1
225
219
23
216
6
225
5
14
17
57930
247
17
11
...

result:

ok 258 lines

Test #23:

score: 0
Accepted
time: 1070ms
memory: 9892kb

input:

52117 188894
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

18158
16344
26191
34198
12698
33099
15027
22477
17386
23441
36612
37651
33783
34532
16777
44413
24364
21370
30529
49724
47220
33017
28454
10252
42074
7464
34933
26156
22524
25521
33472
10422
26670
15771
22323
36868
20066
21121
44693
46430
44305
36731
15059
3862
17439
22691
7997
34970
22986
36187
843...

result:

ok 188894 lines

Test #24:

score: 0
Accepted
time: 187ms
memory: 10412kb

input:

66038 176476
1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 3 1 2 1 6 1 2 3 2 7 4 1 4 3 2 9 4 11 3 1 1 1 4 4 2 1 3 3 1 2 2 4 15 5 6 9 7 2 2 1 5 3 6 6 1 17 9 5 4 5 1 2 8 2 12 2 5 3 8 2 17 4 1 10 5 5 4 14 15 1 8 12 19 8 2 3 26 1 8 9 2 1 2 7 10 3 20 10 3 13 5 1 9 5 8 11 1 3 4 10 1 19 8 5 1 16 5 17 17 33 3 4 1 1...

output:

17
538
582
542
515
539
521
480
537
547
62577
22
424
491
11
445
496
484
457
435
472
433
446
412
423
440
460
428
405
425
8
413
389
404
31
388
346
397
20
10
36
1
381
39
374
305
14
399
23
64
392
370
349
347
328
371
368
396
348
374
266
7
363
312
387
386
38
368
287
365
315
24
326
370
5
309
363
319
345
362...

result:

ok 821 lines

Test #25:

score: 0
Accepted
time: 81ms
memory: 9976kb

input:

73751 186505
1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 2 2 1 1 1 1 2 1 1 1 2 1 1 1 1 1 4 1 1 1 2 1 4 3 4 1 1 3 2 2 2 3 6 3 5 4 1 1 7 4 1 2 2 2 2 8 2 1 2 2 6 3 3 5 1 10 2 2 2 9 1 4 2 5 5 7 2 1 5 3 3 1 2 1 3 2 5 3 3 3 6 4 6 5 2 3 10 11 2 4 7 10 6 5 11 6 7 2 3 13 2 9 22 2 4 8 1 7 2 11 6 1 1 4 9 5 9 9 1 6 1 17 5 ...

output:

73
82
74
78
80
78
78
80
75
71
75
72
71
74
71
72
76
71
71
80
74
67
65
68
68
67
63
64
67
65
60
68
73
69
68
61
63
62
53
59
60
62
58
64
55
59
61
61
60
60
53
55
57
62
59
59
59
47
53
56
50
51
55
54
58
48
54
51
53
54
55
53
51
43
46
56
52
53
44
42
45
49
46
49
47
52
51
46
45
39
51
54
42
42
51
42
44
39
45
42
...

result:

ok 20722 lines

Test #26:

score: 0
Accepted
time: 2397ms
memory: 8452kb

input:

73031 196038
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

47364
37196
32868
11129
17755
16034
16750
6247
5189
13981
14125
11643
1348
10528
9300
10119
8642
8054
8827
72770
8967
641
8506
6422
6981
7356
7286
1180
6836
6083
1231
194
7070
6895
7208
6444
6100
6264
2550
401
5719
5626
630
4788
5505
4681
4864
41770
5100
504
4128
4191
4057
4267
5301
4175
71899
4486
...

result:

ok 167 lines

Test #27:

score: 0
Accepted
time: 92ms
memory: 9944kb

input:

81574 196519
1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 4 1 4 1 2 3 1 2 1 2 1 3 1 2 1 4 6 1 1 2 1 8 1 1 3 9 2 1 5 6 3 4 10 6 2 1 12 6 2 5 13 9 1 4 4 2 4 1 4 7 2 1 5 3 5 1 5 1 8 7 2 2 14 2 11 21 14 3 7 5 3 4 9 8 5 4 20 2 6 10 4 7 3 6 1 2 2 2 7 8 1 1 2 10 6 11 3 1 25 4 12 12 10 4 16 3 5 7 1 6 6 7 3 28 15 4 3 20 8 ...

output:

56
64
60
58
62
62
56
61
57
66
59
63
60
60
57
62
57
58
57
59
58
61
62
59
48
49
63
51
62
59
55
52
54
59
59
59
58
58
63
56
58
48
62
54
53
59
58
57
62
56
55
55
49
52
62
50
53
51
47
56
54
45
59
50
51
53
39
50
49
55
45
53
47
43
54
54
63
48
55
50
47
50
46
42
49
48
44
48
43
38
41
44
47
47
48
44
52
47
45
51
...

result:

ok 32753 lines

Test #28:

score: 0
Accepted
time: 310ms
memory: 10384kb

input:

85913 189305
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 3 1 2 3 2 2 2 1 1 2 1 1 1 3 5 3 3 4 2 2 2 3 2 3 1 2 3 1 6 2 1 2 1 1 2 3 8 5 3 8 2 1 4 2 5 6 1 1 12 3 2 1 7 6 2 2 3 1 1 2 5 4 6 9 1 8 8 9 4 14 10 9 15 8 5 2 13 5 14 2 12 7 2 20 4 14 7 4 13 9 10 5 11 1 5 4 2 1 2 7 4 3 1 6 4 2 21 1 2 9 20 7 7 4 2 7 1...

output:

642
8295
593
35
112
83243
11
576
608
34
18
39
584
533
501
516
532
2485
82892
54
79315
9
85168
487
81000
419
422
1121
84890
85374
433
455
115
431
12114

result:

ok 35 lines

Test #29:

score: 0
Accepted
time: 79ms
memory: 7916kb

input:

89431 189439
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 4 1 2 2 2 6 1 2 4 1 2 1 5 1 1 1 1 1 1 5 6 2 6 5 1 2 2 2 5 2 4 1 4 3 2 5 5 3 3 1 2 1 7 1 5 4 4 1 1 9 1 1 5 3 3 7 10 9 1 5 2 1 6 8 8 6 7 3 3 10 6 12 4 15 10 3 2 2 12 1 19 8 10 12 3 2 7 2 1 1 4 14 19 5 10 9 3 30 2 4 7 3 1 2 1 2 1 7 12 4 11 6 1 7 8 6 8 9 ...

output:

43
47
49
46
43
47
45
48
50
41
44
41
49
43
43
44
40
48
43
41
42
43
42
36
45
41
41
39
45
43
42
43
41
41
46
43
46
42
43
34
42
43
44
45
39
48
42
36
43
40
43
45
39
38
37
35
40
37
44
40
40
44
35
32
41
37
40
43
37
41
37
40
42
35
37
39
41
32
44
36
40
38
40
38
30
39
41
34
38
45
33
34
40
43
41
40
38
35
32
33
...

result:

ok 37887 lines

Test #30:

score: 0
Accepted
time: 244ms
memory: 10412kb

input:

86886 199524
1 1 1 1 1 1 1 1 1 1 1 1 2 3 1 1 2 1 2 1 4 3 4 1 2 5 7 1 3 3 3 2 6 2 5 2 3 3 2 2 5 1 5 4 3 1 1 1 2 1 2 5 1 2 5 2 1 1 6 3 2 5 2 4 6 4 15 2 7 10 1 6 4 1 5 1 6 2 8 4 2 1 8 6 8 3 16 8 6 7 1 2 1 1 3 2 6 1 3 1 10 4 1 9 4 3 2 6 7 6 4 17 2 13 2 1 2 9 8 4 2 11 11 19 3 1 16 19 2 17 10 16 3 1 3 24 ...

output:

650
16
555
564
83736
591
550
32
148
487
7
91
49
32
502
498
29
17
455
7
12
455
442
392
13
15
417
80904
29
426
63
52
426
415
400
385
382
425
78
84506
348
416
377
384
385
431
2285
426
384
358
416
13
355
399
398
390
378
17
17
12
402
397
376
391
10
10
377
373
380
398
397
368
399
368
362
339
21
44
365
379...

result:

ok 176 lines

Test #31:

score: 0
Accepted
time: 98ms
memory: 9924kb

input:

95660 187672
1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 3 1 1 2 5 3 3 6 4 4 1 1 1 5 4 3 2 3 4 7 7 1 1 3 6 1 6 1 1 6 17 1 4 4 10 5 10 6 5 1 1 2 8 8 9 23 4 3 6 9 8 1 1 1 3 2 1 1 1 4 3 1 4 12 3 18 2 3 3 2 6 1 21 2 7 8 8 2 1 5 9 10 21 6 7 6 3 19 9 5 1 7 1 15 2 8 8 3 1 9 6 6 7 2 11 15 44 4 5 24 13 21 1 16 1...

output:

100
91
95
100
94
94
89
93
86
86
92
88
95
85
92
96
89
91
95
83
84
84
84
86
87
82
82
90
80
88
80
90
85
81
87
80
84
87
90
81
78
84
77
76
84
76
91
78
78
85
82
77
74
80
86
80
81
81
80
72
84
76
71
68
71
71
77
73
73
71
68
72
67
80
71
74
66
73
75
68
78
73
76
71
80
72
62
67
71
79
66
67
72
67
56
72
74
66
68
6...

result:

ok 18767 lines

Test #32:

score: -100
Time Limit Exceeded

input:

86200 196707
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:


result: