QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386195#7448. rfplcaKevin5307AC ✓1545ms35456kbC++232.7kb2024-04-11 13:55:532024-04-11 13:55:55

Judging History

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

  • [2024-04-11 13:55:55]
  • 评测
  • 测评结果:AC
  • 用时:1545ms
  • 内存:35456kb
  • [2024-04-11 13:55:53]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
ll val[400400],tag[400400];
int n,q;
const int B=500;
void update(int l,int r,ll v)
{
	int lb=l/B,rb=r/B;
	if(lb==rb)
	{
		for(int i=l;i<=r;i++)
			val[i]+=v;
		return ;
	}
	for(int i=l;i/B==lb;i++)
		val[i]+=v;
	for(int i=r;i/B==rb;i--)
		val[i]+=v;
	for(int i=lb+1;i<rb;i++)
		tag[i]+=v;
}
inline ll query(int p)
{
	if(p<=1) return 0;
	return max(1ll,val[p]+tag[p/B]);
}
int lst[400400];
int nxt[400400],prv[400400];
bool ok[400400];
int tp[400400];
inline int get_lst(int x)
{
	return query(tp[x]);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=2;i<=n;i++)
	{
		int f;
		cin>>f;
		update(i,i,f);
	}
	set<int> st;
	for(int i=2;i<=n;i++)
	{
		int f=query(i);
		if(f/B!=i/B)
		{
			lst[i]=f;
			ok[i]=1;
			tp[i]=i;
		}
		else
		{
			lst[i]=lst[f];
			tp[i]=tp[f];
			if(sz(st))
			{
				nxt[*st.rbegin()]=i;
				prv[i]=*st.rbegin();
			}
			st.insert(i);
		}
	}
	if(sz(st)) nxt[*st.rbegin()]=n+1;
	int lastans=0;
	while(q--)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int l,r,x;
			cin>>l>>r>>x;
			l^=lastans;
			r^=lastans;
			x^=lastans;
			update(l,r,-x);
			auto it=st.lower_bound(l);
			if(it==st.end()||*it>r) continue;
			int cur=*it;
			while(cur<=n&&cur/B<=r/B)
			{
				int f=query(cur);
				if(f/B!=cur/B)
				{
					lst[cur]=f;
					tp[cur]=cur;
					st.erase(cur);
					ok[cur]=1;
					prv[nxt[cur]]=prv[cur];
					nxt[prv[cur]]=nxt[cur];
				}
				else
				{
					lst[cur]=get_lst(f);
					tp[cur]=tp[f];
				}
				cur=nxt[cur];
			}
		}
		else
		{
			int u,v;
			cin>>u>>v;
			u^=lastans;
			v^=lastans;
			int u2=-1,v2=-1;
			while((u2=get_lst(u))!=(v2=get_lst(v))||u/B!=v/B)
			{
				if(u/B!=v/B)
				{
					if(u<v)
					{
						swap(u,v);
						swap(u2,v2);
					}
					u=u2;
					continue;
				}
				if(u2<v2)
				{
					swap(u,v);
					swap(u2,v2);
				}
				u=u2;
			}
			while(u!=v)
			{
				if(u<v) swap(u,v);
				u=query(u);
			}
			cout<<(lastans=u)<<'\n';
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 212ms
memory: 14144kb

input:

400000 400000
1 2 1 4 1 1 5 4 6 5 9 1 1 13 3 8 12 16 3 11 8 8 2 18 21 15 7 23 11 6 4 26 17 5 12 6 5 28 32 26 21 5 19 1 25 25 11 26 47 11 31 25 18 7 25 36 40 23 54 31 14 62 61 33 57 40 11 16 24 51 69 25 55 51 55 65 34 19 18 21 20 62 64 83 22 48 67 47 21 27 30 63 10 14 70 63 18 17 74 98 40 89 10 7 30 ...

output:

1
1
1
1
1
1
4
1
1
1
4
1
1
18
1
4
1
18
1
1
4
1
1
1
1
5
1
4
4
4
11
5
1
4
1
4
1
1
4
1
1
1
4
1
1
1
1
4
4
1
1
1
4
4
1
1
1
1
4
1
1
1
5
1
1
1
1
5
1
1
1
1
4
1
1
12
12
1
1
4
1
1
11
1
1
1
1
4
1
1
1
4
1
1
1
14
1
18
7
5
25
1
62
1
1
1
1
1
1
1
4
4
4
102
1
1
1
1
1
2
1
1
1
1
1
1
1
1
18
4
1
1
4
5
1
1
1
1
1
1
1
1
1
1...

result:

ok 200476 lines

Test #2:

score: 0
Accepted
time: 847ms
memory: 32916kb

input:

400000 400000
1 1 1 1 1 1 1 1 1 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 9...

output:

1
1
289629
1
1
37362
1
1
1
1
1
2107
1
1
1
1
1
200528
1
1
1
1
1
1
1
1
1
11646
1
1
1
1
7608
1
1
1
1
1
12297
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
206102
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
234105
1
213107
1
1
1
1
47884
1
1
1
1
1
1
1
1
1
1
1
4725
1
1
1
2170
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
206097
1
...

result:

ok 199431 lines

Test #3:

score: 0
Accepted
time: 1114ms
memory: 33184kb

input:

400000 400000
1 2 2 4 4 5 7 7 9 10 11 12 13 14 15 15 16 17 18 20 20 22 22 23 24 26 27 27 28 30 31 32 32 33 35 35 37 38 38 40 41 41 42 43 45 45 46 47 49 49 51 52 53 53 54 56 57 58 58 60 60 61 63 64 64 65 66 68 68 70 71 71 72 73 75 75 76 78 79 79 81 81 82 83 85 85 87 88 88 90 91 92 92 94 95 95 96 98 9...

output:

210801
160667
149084
223804
42542
53089
15189
225821
254995
20768
39457
47988
79032
79157
32888
132798
56834
104162
380609
81459
27942
15916
76220
122556
5183
310812
148803
188513
211433
26186
271890
236458
281943
294363
101756
132671
61499
79360
30593
172339
261927
78569
135362
217756
23629
227179
...

result:

ok 200314 lines

Test #4:

score: 0
Accepted
time: 1148ms
memory: 33040kb

input:

400000 400000
1 1 3 3 1 1 6 3 1 5 9 8 4 14 15 16 17 14 13 16 14 22 14 24 20 18 21 23 22 22 22 29 32 30 29 29 36 32 32 38 36 33 38 43 44 45 45 46 48 45 45 49 48 51 49 49 48 55 51 54 52 56 61 60 61 60 65 64 66 66 62 66 69 73 66 75 71 77 77 79 75 81 79 76 85 83 86 86 82 83 83 89 87 87 90 92 97 94 94 92...

output:

66536
42746
75273
60596
395361
75345
176775
11033
45502
92873
10536
28053
95739
65423
23980
148212
148187
68177
95384
240392
167540
203213
115465
170774
55225
159774
117049
31929
63997
20775
168687
18075
230893
55461
8262
180040
126544
12538
157569
254873
43232
212315
165491
46473
21093
169898
7139
...

result:

ok 200328 lines

Test #5:

score: 0
Accepted
time: 754ms
memory: 33116kb

input:

400000 400000
1 1 1 3 3 4 6 8 8 10 10 10 12 14 14 15 15 16 17 19 21 20 22 23 24 24 26 27 27 30 31 31 32 34 33 36 35 37 38 40 39 42 41 42 44 46 45 47 49 48 50 51 51 53 53 55 57 56 59 59 60 60 63 64 63 66 65 66 67 70 69 71 71 74 75 76 77 77 79 79 80 80 83 83 85 86 86 86 88 89 91 91 92 92 94 96 96 96 9...

output:

176159
114275
14085
231014
132050
95691
93758
210575
14952
83916
274682
13907
105473
48151
155526
90678
53411
182975
221031
126955
150326
307833
68995
166787
49652
104548
236019
113064
132156
65611
85394
34656
117176
608
190709
175534
95813
174875
192078
165010
183694
208180
24346
152280
314154
2491...

result:

ok 200095 lines

Test #6:

score: 0
Accepted
time: 695ms
memory: 32976kb

input:

400000 400000
1 1 3 3 1 1 6 3 1 5 9 8 4 14 15 16 17 14 13 16 14 22 14 24 20 18 21 23 22 22 22 29 32 30 29 29 36 32 32 38 36 33 38 43 44 45 45 46 48 45 45 49 48 51 49 49 48 55 51 54 52 56 61 60 61 60 65 64 66 66 62 66 69 73 66 75 71 77 77 79 75 81 79 76 85 83 86 86 82 83 83 89 87 87 90 92 97 94 94 92...

output:

265110
56921
177951
17569
11033
64259
70004
25947
80353
54746
65423
48917
161026
68177
264589
170774
77420
31929
94829
53873
168687
18075
21563
163635
51540
224275
114283
62827
126544
288274
12538
15780
209938
155113
3981
339925
79736
195100
97468
73031
103710
91813
118003
241688
138289
66328
182956...

result:

ok 199399 lines

Test #7:

score: 0
Accepted
time: 866ms
memory: 35164kb

input:

400000 400000
1 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...

output:

1
1
1
1
318434
1
1
143691
1
210125
1
1
13713
175331
1
1
1
1
1
11022
1
1
22733
1
1
210126
9546
134986
1
124872
1
103369
1
108106
42169
40449
1
1
8253
179436
142152
39135
1
121851
27988
1
1
1
63210
1
1
9626
1
1
121241
203789
1012
1
145550
1
86090
25925
1
1
95571
1
27060
197787
1
93637
200256
114145
34...

result:

ok 199398 lines

Test #8:

score: 0
Accepted
time: 795ms
memory: 31444kb

input:

400000 400000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 3...

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
187326
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 199964 lines

Test #9:

score: 0
Accepted
time: 1545ms
memory: 33408kb

input:

400000 400000
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 9...

output:

91
82
94
91
93
52
45
29
31
36
27
59
19
17
64
1
1
1
1
1
1
1
29
1
1
1
1
1
41
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
22
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
115623
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
133037
1
1
1
1
1
1
1
47
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 40000 lines

Test #10:

score: 0
Accepted
time: 1541ms
memory: 33152kb

input:

400000 400000
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 9...

output:

191
182
178
165
185
162
173
166
165
127
127
168
137
144
64
131
105
115
37
61
168
168
29
54
112
1
133
1
41
121
141
81
95
65
1
35
1
86
1
1
129
1
61
1
1
123
1
1
22
1
1
1
1
1
1
1
1
1
1
1
103
1
1
1
1
1
115623
1
1
1
1
1
1
1
1
1
1
1
71
1
1
1
1
1
133037
1
1
1
1
1
1
1
47
1
1
1
1
1
1
1
1
1
1
1
68
1
1
1
1
1
1
...

result:

ok 40000 lines

Test #11:

score: 0
Accepted
time: 1516ms
memory: 35196kb

input:

400000 400000
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 9...

output:

291
291
290
276
277
272
237
239
247
218
227
277
187
271
200
176
259
278
143
242
168
168
237
138
112
178
133
252
41
121
141
81
95
65
1
35
1
86
1
136
129
177
61
120
1
123
1
1
22
180
186
1
1
1
1
107
1
1
1
65
103
1
21
1
1
1
115623
115
1
1
1
1
1
1
1
1
1
1
71
1
1
1
1
1
133037
1
1
1
1
1
1
1
47
1
1
1
1
1
1
...

result:

ok 40000 lines

Test #12:

score: 0
Accepted
time: 546ms
memory: 35456kb

input:

400000 400000
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 9...

output:

195546
142231
188299
113064
129034
107442
113059
87306
63779
71726
131225
91431
101847
18176
36879
45704
67500
24079
24080
46574
24079
24079
24079
158137
24080
53649
52451
24079
99
24080
24079
52451
52450
24079
24079
24079
24080
1435
24079
1345
1347
1344
1344
1346
86326
1345
1345
257181
98837
1345
1...

result:

ok 200482 lines

Test #13:

score: 0
Accepted
time: 1489ms
memory: 33148kb

input:

400000 400000
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 9...

output:

391
386
374
387
369
345
365
385
329
309
327
291
305
285
336
276
259
278
315
242
358
367
237
271
338
178
377
252
303
149
141
370
131
190
316
150
167
86
337
136
129
177
61
120
123
123
249
252
22
180
186
1
1
1
88
107
165
104
1
65
103
340
21
1
45
1
115623
115
1
1
1
1
1
1
1
1
1
1
71
266
14
1
1
1
133037
1...

result:

ok 40000 lines

Test #14:

score: 0
Accepted
time: 881ms
memory: 33220kb

input:

400000 400000
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 9...

output:

491
481
486
463
461
455
441
458
441
420
427
400
423
398
371
421
413
441
381
423
358
367
445
355
338
413
377
252
303
392
421
370
393
372
316
360
167
157
337
216
131
177
193
120
123
123
249
252
97
180
186
401
29
316
88
107
165
104
287
65
103
340
21
1
45
1
115623
115
153
226
1
146
1
1
1
1
1
1
71
266
14...

result:

ok 40000 lines

Test #15:

score: 0
Accepted
time: 980ms
memory: 33156kb

input:

400000 400000
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 9...

output:

591
581
573
572
557
547
557
531
523
511
527
495
491
525
472
466
567
441
487
423
548
566
445
488
564
413
377
505
565
392
421
370
393
372
316
360
318
429
337
497
499
237
449
246
375
538
249
252
464
180
186
401
473
316
324
107
165
104
287
65
103
340
205
488
45
75
115623
115
153
226
1
146
1
1
1
1
1
423
...

result:

ok 40000 lines

Test #16:

score: 0
Accepted
time: 914ms
memory: 33204kb

input:

400000 400000
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 9...

output:

691
690
682
683
691
657
685
677
657
673
627
604
609
652
608
566
567
604
553
604
548
566
653
488
564
648
621
505
565
663
421
659
429
497
632
475
501
429
365
497
499
556
449
517
375
538
365
360
464
631
245
401
473
316
324
253
335
326
287
220
653
340
205
488
386
574
115623
115
153
226
310
146
373
610
2...

result:

ok 40000 lines

Test #17:

score: 0
Accepted
time: 380ms
memory: 15568kb

input:

100000 100000
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 9...

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 100000 lines

Test #18:

score: 0
Accepted
time: 1135ms
memory: 33144kb

input:

400000 400000
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 9...

output:

30464
209869
346131
58298
87306
91431
324429
335615
71727
272855
203724
126725
49227
324366
262038
263155
69277
97745
86853
114040
24040
218806
101585
41582
26712
76484
209740
270655
126128
247387
100189
276196
154229
73723
211621
4636
192962
258268
116999
230952
258737
229156
110595
65655
92774
783...

result:

ok 200202 lines

Test #19:

score: 0
Accepted
time: 239ms
memory: 14036kb

input:

400000 400000
1 2 1 4 1 1 5 4 6 5 9 1 1 13 3 8 12 16 3 11 8 8 2 18 21 15 7 23 11 6 4 26 17 5 12 6 5 28 32 26 21 5 19 1 25 25 11 26 47 11 31 25 18 7 25 36 40 23 54 31 14 62 61 33 57 40 11 16 24 51 69 25 55 51 55 65 34 19 18 21 20 62 64 83 22 48 67 47 21 27 30 63 10 14 70 63 18 17 74 98 40 89 10 7 30 ...

output:

1
1
1
1
4
4
1
1
1
1
1
1
1
1
274
1
1
1
1
1
1
4
1
5
1
1
1
4
4
1
40
1
1
4
1
1
1
4
1
4
1
1
4
1
8
1
4
1
5
4
1
5
1
4
1
4
1
1
1
1
7
183
4
1
1
1
1
1
4
4
5
4
4
18
4
1
12
1
1
1
4
4
1
5
1
1
1
1
4
5
4
23
4
1
1
11
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
4
1
5
1
1
1
1
4
127
1
1
4
4
1
4
1
1
4
1
12
11
12
1
4
1
1
1
...

result:

ok 199826 lines

Test #20:

score: 0
Accepted
time: 194ms
memory: 14608kb

input:

400000 400000
1 2 1 4 1 1 5 4 6 5 9 1 1 13 3 8 12 16 3 11 8 8 2 18 21 15 7 23 11 6 4 26 17 5 12 6 5 28 32 26 21 5 19 1 25 25 11 26 47 11 31 25 18 7 25 36 40 23 54 31 14 62 61 33 57 40 11 16 24 51 69 25 55 51 55 65 34 19 18 21 20 62 64 83 22 48 67 47 21 27 30 63 10 14 70 63 18 17 74 98 40 89 10 7 30 ...

output:

1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200476 lines

Test #21:

score: 0
Accepted
time: 1034ms
memory: 33144kb

input:

400000 400000
1 1 1 3 3 4 6 8 8 10 10 10 12 14 14 15 15 16 17 19 21 20 22 23 24 24 26 27 27 30 31 31 32 34 33 36 35 37 38 40 39 42 41 42 44 46 45 47 49 48 50 51 51 53 53 55 57 56 59 59 60 60 63 64 63 66 65 66 67 70 69 71 71 74 75 76 77 77 79 79 80 80 83 83 85 86 86 86 88 89 91 91 92 92 94 96 96 96 9...

output:

101073
211829
326427
107757
119987
176159
10989
282713
87073
14085
231008
132050
19163
46545
84563
71799
58338
257776
185047
88731
17459
90678
196587
69916
179292
42914
323586
52162
140364
228808
180551
125544
68711
113064
152699
231292
192479
39818
14221
237320
85394
34656
40186
117176
20260
147942...

result:

ok 200289 lines

Test #22:

score: 0
Accepted
time: 794ms
memory: 35232kb

input:

400000 400000
1 2 2 4 4 5 7 7 9 10 11 12 13 14 15 15 16 17 18 20 20 22 22 23 24 26 27 27 28 30 31 32 32 33 35 35 37 38 38 40 41 41 42 43 45 45 46 47 49 49 51 52 53 53 54 56 57 58 58 60 60 61 63 64 64 65 66 68 68 70 71 71 72 73 75 75 76 78 79 79 81 81 82 83 85 85 87 88 88 90 91 92 92 94 95 95 96 98 9...

output:

161262
3721
42542
15189
362730
214568
116266
311821
351437
24200
63424
56834
104162
209382
15916
232797
232733
178403
620
257291
236002
305819
257291
132671
314616
30593
261930
147
164897
68758
153842
229733
61550
74335
162103
215815
252933
221564
91911
126631
233858
183265
155428
313622
20954
94438...

result:

ok 199414 lines

Test #23:

score: 0
Accepted
time: 881ms
memory: 35116kb

input:

400000 400000
1 1 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 ...

output:

1
210416
7885
1
216008
36186
146716
1
1
217702
183830
1
213656
1
1
232671
1
1
1
173279
163087
1
69971
100996
1
1
1
1
1
1
1
1
1
71396
1
1
1
1
1
1
1
1
160231
131210
1
1
161995
1
1
1
1
200543
1
10552
1
1
1
16813
1
1
1
1
1
1
1
1
1
1
1
1
1
45381
1
1
1
148081
102158
1
1
1
1
1
103798
1
177666
40784
203246
...

result:

ok 200064 lines