QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#713945#5173. 染色int_R100 ✓495ms106120kbC++141.1kb2024-11-05 20:59:252024-11-05 20:59:25

Judging History

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

  • [2024-11-05 20:59:25]
  • 评测
  • 测评结果:100
  • 用时:495ms
  • 内存:106120kb
  • [2024-11-05 20:59:25]
  • 提交

answer

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int MAXN=1e6+10;
int n,Q,a[MAXN],cur=MAXN,p[MAXN],w[MAXN];
int fa[MAXN],siz[MAXN],pos[MAXN],ans[MAXN];
vector <int> v[MAXN];vector <pair<int,int>> g[MAXN];
inline int find(int x)
	{return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y)
{
	int fax=find(x),fay=find(y);
	if(siz[fax]>siz[fay]) swap(fax,fay);
	fa[fax]=fay,pos[fay]=y,siz[fay]+=siz[fax];
}
signed main()
{
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>Q;
	for(int i=1;i<=n;++i) cin>>a[i],pos[i]=fa[i]=i,siz[i]=1;
	for(int i=n;i;--i)
	{
		if(p[a[i]]) cur=min(cur,p[a[i]]);p[a[i]]=i;
		if(cur!=MAXN) w[i]=w[cur]+1,v[cur].push_back(i);
	}
	for(int i=1,l,r;i<=Q;++i)
	{
		cin>>l>>r;if(l>r) swap(l,r);
		g[r].push_back({l,i}),ans[i]=2*(r-l);
	}
	for(int i=1;i<=n;++i)
	{
		for(int y:v[i]) merge(y,i);
		for(auto now:g[i])
			ans[now.second]-=w[now.first]-w[pos[find(now.first)]];
	}
	for(int i=1;i<=Q;++i) cout<<ans[i]<<'\n';return 0;
}

詳細信息

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 7ms
memory: 60564kb

input:

10000 100
84 85 52 2 78 53 20 21 23 76 37 44 18 5 37 8 81 65 46 58 69 1 69 37 53 46 37 35 35 89 1 77 35 6 46 59 89 46 25 55 50 38 61 67 44 23 29 24 46 4 42 15 34 77 20 34 83 79 12 50 69 26 38 14 9 66 80 72 22 26 9 68 35 38 19 84 92 30 83 62 100 71 81 60 7 37 64 50 33 60 86 75 45 78 32 53 3 48 87 60 ...

output:

3668
4575
5976
8382
729
7013
183
7320
492
1140
253
2249
13226
6254
456
7507
2162
10481
1791
2675
4801
293
5997
627
6654
6179
11414
2712
3157
7836
17782
511
5486
17835
9564
6147
4996
14577
670
463
15613
12669
8872
7833
10987
6603
6399
5023
9102
8529
2173
10299
2694
12537
4958
2144
8809
1907
6476
2828...

result:

ok 100 tokens

Test #2:

score: 3
Accepted
time: 7ms
memory: 59424kb

input:

10000 100
84 17 43 100 30 77 73 68 15 91 62 47 89 90 53 43 67 81 64 54 88 88 22 31 76 38 17 87 93 31 67 43 50 27 40 70 43 55 73 82 8 15 64 3 28 27 30 56 1 82 40 51 21 71 74 45 20 99 66 40 99 27 47 65 82 31 43 50 18 48 23 67 56 57 34 39 84 55 66 22 12 83 87 56 15 1 92 26 71 60 76 41 27 32 47 47 5 83 ...

output:

2917
8523
9021
3406
7965
4359
3941
5506
1084
1614
481
81
4058
2180
5726
1694
731
3824
6639
3600
3929
622
10583
8213
7195
14275
5000
10076
11773
9826
11101
584
13966
3123
4956
16159
11421
1277
9028
15023
9857
7385
2167
12910
2557
2507
4890
4412
8218
2327
491
9487
814
3470
13399
4675
13129
17628
2654
...

result:

ok 100 tokens

Test #3:

score: 3
Accepted
time: 7ms
memory: 59284kb

input:

10000 100
32 36 55 41 29 97 62 59 25 9 39 50 64 10 8 63 18 20 92 96 74 39 54 39 21 64 99 42 78 36 89 96 81 41 73 41 79 14 29 52 20 68 98 27 12 25 79 32 43 38 76 84 34 62 23 48 33 63 38 62 38 16 6 80 34 90 78 85 34 4 66 14 72 58 87 97 8 36 45 49 72 7 58 39 60 32 1 58 31 4 96 73 67 17 65 93 36 34 82 8...

output:

915
7882
4456
5090
11266
13587
10142
1715
9756
10320
10688
10946
1041
6819
7585
11004
2376
4515
9410
14700
11609
1002
3283
5657
11717
3351
5542
2648
8219
211
10706
6756
1920
15593
9567
1829
2192
15856
9371
5313
11960
1845
1151
14764
5195
700
7592
2487
13781
3557
5660
3063
1234
1026
10701
13399
8886
...

result:

ok 100 tokens

Test #4:

score: 3
Accepted
time: 10ms
memory: 60640kb

input:

10000 100
1 11 1 48 3 13 2 49 2 98 3 41 3 29 3 1 3 28 3 64 1 86 2 62 3 47 1 51 1 4 3 11 2 17 3 41 1 5 2 71 1 63 2 38 1 41 3 86 1 38 2 25 1 56 2 64 1 58 2 3 2 96 1 57 1 37 3 98 2 84 2 30 3 20 1 42 2 29 1 26 3 63 2 43 2 67 3 76 1 86 3 82 2 57 1 11 3 72 1 97 1 50 3 78 3 96 3 3 2 89 1 52 2 4 1 79 2 8 1 ...

output:

3247
4211
7240
9159
5437
560
1806
7335
9493
178
2975
5263
4077
9925
2564
5853
6617
7426
472
4861
70
3717
2587
5337
11345
4078
4262
1374
8587
8758
247
8562
10193
967
6174
1331
14658
3522
4343
6363
15336
1626
7881
5480
5926
130
14564
3918
9515
1625
1700
2996
8011
10032
3195
13157
14630
5981
5568
5635
...

result:

ok 100 tokens

Test #5:

score: 3
Accepted
time: 7ms
memory: 59888kb

input:

10000 100
1 75 2 61 1 93 1 74 2 100 1 3 3 46 2 35 3 67 1 78 1 23 2 75 2 76 2 86 3 95 1 23 1 97 1 82 1 32 2 37 1 1 1 11 1 70 1 95 3 88 3 94 3 97 3 39 3 8 2 90 2 13 3 41 3 33 3 50 3 13 3 87 3 18 2 47 2 41 2 44 1 94 1 87 3 60 2 86 1 70 2 75 2 44 2 17 2 95 2 90 2 76 3 3 1 28 3 66 2 65 1 48 1 2 1 63 1 10...

output:

10931
533
3443
1214
1825
4206
7142
1472
1562
6028
618
9559
501
2796
12337
3511
12351
5459
13074
8159
4684
2508
11605
8231
11646
5209
1175
6346
2665
4952
12436
4120
3712
3069
10795
3114
2912
12743
6998
1822
9440
7080
1930
431
294
6709
6148
7049
6792
1813
11850
13314
74
8352
5258
3855
2678
6790
9055
6...

result:

ok 100 tokens

Test #6:

score: 3
Accepted
time: 0ms
memory: 59404kb

input:

10000 100
4 73 53 79 63 67 22 41 3 90 3 11 86 58 81 98 66 31 92 51 25 27 90 95 57 65 1 73 21 11 4 44 5 26 2 2 72 1 46 80 24 20 42 58 48 34 84 66 35 86 56 30 2 68 68 74 59 9 32 3 68 1 98 75 17 6 55 24 67 34 56 23 55 75 56 69 26 11 35 55 54 87 96 56 4 39 61 4 92 7 24 96 88 7 95 15 88 52 59 62 72 9 20 ...

output:

18957
19017
18891
19110
18997
18929
18891
19005
19012
18956
18985
18915
19071
18829
18922
18972
19072
19037
18966
19018
18854
19006
19083
18868
19015
18961
18905
18797
19029
18906
19053
19041
18919
19100
18893
19008
18986
18920
18972
18961
18967
18970
19029
19041
18953
18919
19126
19109
19137
19022
...

result:

ok 100 tokens

Subtask #2:

score: 13
Accepted

Test #7:

score: 13
Accepted
time: 38ms
memory: 65404kb

input:

100000 100000
3 2 3 3 3 3 2 3 2 1 3 1 1 1 3 2 1 3 1 2 2 1 3 1 2 2 1 1 1 3 2 1 3 3 3 3 1 1 1 2 3 3 2 1 1 1 3 1 3 1 3 2 1 3 2 3 3 2 3 3 2 3 3 3 3 3 2 3 2 3 1 3 3 3 3 3 3 3 1 2 3 3 1 3 1 1 2 2 3 1 1 2 3 2 3 1 3 2 1 3 2 3 2 1 1 3 3 1 3 1 2 2 2 3 2 3 2 3 2 1 1 3 1 3 2 2 3 3 3 1 2 2 3 3 2 1 3 1 2 2 2 3 2 ...

output:

113194
133099
54921
6483
9199
78290
93920
29192
38941
111588
66619
7226
66019
42776
44640
49274
11102
107722
71676
10708
4735
87161
46860
75805
27270
10951
12237
59513
18641
55105
11626
7850
5521
38727
67276
58326
16941
70130
70341
53673
51864
551
18481
119885
4016
43296
62515
33972
9870
24982
33222...

result:

ok 100000 tokens

Test #8:

score: 13
Accepted
time: 28ms
memory: 66224kb

input:

100000 100000
2 3 2 2 2 1 2 1 2 1 2 2 3 3 3 2 1 2 1 1 3 3 3 1 3 1 1 1 2 2 1 1 3 3 3 2 2 2 1 3 3 3 3 3 3 2 1 3 2 1 3 3 1 1 1 2 3 1 1 3 3 2 1 1 2 2 2 1 3 1 1 3 2 2 1 2 2 3 2 1 1 1 1 1 1 2 2 3 3 2 1 3 3 2 3 2 1 2 3 3 1 3 1 3 3 1 3 3 1 3 1 1 3 2 3 2 2 2 1 3 2 1 2 1 2 3 3 3 3 3 1 2 2 2 2 1 2 2 3 3 1 2 3 ...

output:

26713
92501
21509
49442
97641
78683
141125
77139
85866
63249
94772
69580
92232
51238
68375
24225
33431
945
69079
81415
89436
46535
15964
5588
93083
42072
99191
79445
79452
91055
38537
37616
422
72269
18476
82679
19235
10612
8002
12362
35849
66190
71653
93753
68380
17858
100447
115325
114262
29272
91...

result:

ok 100000 tokens

Test #9:

score: 13
Accepted
time: 48ms
memory: 63512kb

input:

100000 100000
2 1 1 1 1 1 3 1 3 1 1 1 1 1 3 2 1 1 1 2 3 3 3 3 2 1 2 3 3 2 3 3 2 1 1 1 2 3 2 3 1 1 2 2 2 1 3 3 1 3 3 3 2 2 1 1 1 1 1 3 1 1 2 3 3 3 1 3 3 1 1 1 3 2 3 2 1 1 3 2 2 3 1 2 3 3 2 2 2 2 1 2 3 3 3 1 1 1 3 3 3 2 2 3 1 3 3 3 1 1 1 2 1 3 2 1 1 1 2 2 1 3 2 3 2 1 2 1 1 2 1 3 3 3 1 2 3 3 1 2 3 1 1 ...

output:

80639
35808
47971
6829
13146
13817
26698
27049
645
41874
8900
10110
49884
79227
31064
124997
120224
119988
19203
69267
15180
24295
112608
78787
9713
51263
7039
14760
79569
68042
18132
29324
42684
87131
52903
5361
1980
146285
95921
36987
7182
76523
34491
20411
5262
99211
5426
115946
70902
61447
17419...

result:

ok 100000 tokens

Test #10:

score: 13
Accepted
time: 48ms
memory: 67356kb

input:

100000 100000
1 1 3 1 3 2 1 1 2 2 1 2 1 2 2 1 3 3 3 1 3 1 3 2 2 1 3 3 3 1 1 3 3 1 3 2 1 2 2 3 1 1 2 1 2 1 1 2 2 1 2 1 1 2 1 3 3 3 1 3 3 3 2 3 1 2 2 3 2 1 3 2 3 2 1 2 1 2 3 1 2 1 1 1 2 1 1 3 1 1 2 2 1 1 2 1 3 3 2 2 1 1 2 2 3 2 3 1 1 2 2 3 3 1 1 2 1 1 2 3 2 3 2 3 3 3 2 3 1 3 2 2 3 2 3 2 2 1 3 3 1 2 1 ...

output:

38914
124419
25224
129215
32037
25575
62618
95520
22272
59239
29749
68889
103029
33972
4568
74859
114913
100546
51067
49206
49109
51661
41339
9719
64962
11110
16135
87092
65934
104569
61632
47720
14030
33785
20259
34555
69260
77538
8434
13773
58838
30772
30535
107145
4075
30415
88009
44581
24535
557...

result:

ok 100000 tokens

Test #11:

score: 13
Accepted
time: 39ms
memory: 68372kb

input:

100000 100000
2 2 2 3 2 1 1 3 2 3 1 1 3 1 1 2 2 1 2 3 3 3 1 3 1 3 3 1 1 2 1 2 3 2 1 2 2 2 3 2 3 1 3 3 3 2 2 2 1 3 3 1 2 1 3 1 2 2 2 1 2 1 3 3 2 1 3 2 1 2 2 1 3 3 2 2 2 1 2 2 2 2 2 1 2 3 3 3 3 1 1 1 2 1 2 2 1 3 1 1 2 1 1 2 3 2 3 2 3 2 3 1 3 3 2 1 3 1 3 2 3 1 3 1 1 3 1 1 1 1 3 1 3 1 1 1 1 3 1 2 1 1 3 ...

output:

30863
18
28518
72686
68011
26355
45471
35775
65310
90667
88521
55374
31885
17730
81081
30936
26897
57441
72204
23430
10024
26381
25825
44964
61567
107852
44692
63770
28209
44337
8455
6079
55198
40525
51253
59429
4115
59772
25858
18511
36125
78750
97180
76379
15614
41214
98595
94157
24511
87049
2599
...

result:

ok 100000 tokens

Test #12:

score: 13
Accepted
time: 40ms
memory: 65776kb

input:

100000 100000
2 1 2 1 2 2 2 1 2 1 1 2 2 2 2 1 2 1 1 2 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1 1 2 1 1 1 2 1 2 2 2 1 1 1 2 2 2 2 2 2 1 1 1 2 1 2 2 2 1 2 2 1 1 2 1 1 1 2 2 2 1 2 1 2 1 1 1 1 1 2 1 2 1 1 2 2 2 1 1 1 2 1 2 2 2 2 1 1 2 1 2 1 2 2 1 2 2 2 1 1 2 1 1 2 1 2 1 2 1 1 1 1 1 2 1 2 2 2 2 2 2 1 1 2 2 1 1 2 2 ...

output:

126674
35064
19688
42938
32923
73478
59317
35848
61596
99358
38767
18343
8304
23853
24418
4306
80731
60167
34465
70750
19821
8126
78318
77946
42808
2449
114187
26181
86118
30068
48364
71942
42548
42121
127256
69352
33720
57717
23546
4565
78495
27559
89685
25719
53280
16094
7529
38295
69744
15071
101...

result:

ok 100000 tokens

Test #13:

score: 13
Accepted
time: 37ms
memory: 68416kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

44095
8286
11647
7366
41711
67601
10371
14472
80033
39561
3172
66737
19027
39625
6558
54372
60392
50329
41941
20725
19553
4032
29976
28763
69670
23697
83666
22425
56
773
11491
71059
62938
9355
12016
22763
6180
84085
13092
60607
62367
17470
7254
13023
43106
62579
19339
10857
61227
52976
74993
92010
2...

result:

ok 100000 tokens

Test #14:

score: 13
Accepted
time: 33ms
memory: 67852kb

input:

100000 100000
2 3 3 1 1 2 2 3 2 2 1 3 1 1 2 3 1 1 2 3 2 2 1 2 2 2 2 2 3 3 1 3 2 1 1 2 2 1 2 3 2 3 1 1 1 1 1 2 3 3 1 2 1 3 1 3 3 2 2 3 2 1 2 2 2 1 1 2 3 3 3 2 3 1 1 3 1 2 2 3 3 2 2 1 3 2 2 1 3 2 3 3 1 1 1 2 1 3 3 3 3 1 1 1 3 1 2 1 2 2 1 3 2 2 1 1 3 1 3 1 2 1 2 1 1 1 3 1 3 3 2 1 2 1 2 1 2 1 1 1 1 3 1 ...

output:

146007
144884
146532
145483
146702
146484
145964
145344
145303
145612
146416
145526
145260
145480
144927
144670
144864
145021
146735
145109
146401
145323
145373
145564
146806
144932
145976
146202
146193
146108
146360
144421
145270
145317
146273
146588
144281
144679
145584
145336
145709
144910
145783...

result:

ok 100000 tokens

Subtask #3:

score: 18
Accepted

Test #15:

score: 18
Accepted
time: 4ms
memory: 58972kb

input:

5000 5000
256 63 197 36 75 66 33 72 27 75 66 248 29 166 209 252 141 95 84 226 147 249 116 94 192 256 199 273 182 166 116 274 27 211 154 144 283 23 53 110 215 11 164 284 161 221 251 96 43 47 18 115 12 51 156 61 116 209 93 98 47 165 174 106 83 67 184 75 12 290 183 197 112 240 67 56 215 148 104 5 141 2...

output:

1322
2696
1743
2611
4759
4995
2950
1327
880
5076
7811
4860
935
925
808
7270
7663
5325
3813
3225
4478
1577
2540
40
901
300
4351
3882
3813
5739
4610
1658
437
1416
3623
5257
565
119
2044
7615
9112
2047
3121
3683
2883
420
727
4006
179
3231
1443
1602
7127
3008
5954
8083
1539
3807
363
4476
3300
1741
818
2...

result:

ok 5000 tokens

Test #16:

score: 18
Accepted
time: 16ms
memory: 59164kb

input:

5000 5000
180 296 137 108 236 226 19 135 16 42 151 140 223 244 115 170 230 207 143 65 195 219 77 119 170 197 223 65 64 217 206 157 100 52 202 192 19 193 281 229 212 183 63 220 261 66 209 32 63 190 144 221 180 248 29 265 152 141 212 50 129 237 281 270 261 192 104 55 133 12 92 91 61 258 51 172 244 257...

output:

2352
1322
634
560
4251
760
1955
2722
5272
6615
1000
4720
1911
3371
4615
1164
7958
5006
2763
2322
6894
5026
4684
6645
607
5386
1264
7647
2221
651
98
1887
1722
248
954
4149
3969
1388
4170
2436
6737
377
6999
2049
2382
3586
3351
1107
6024
8005
535
1504
4057
438
4064
6837
4173
4865
1903
4334
2962
198
526...

result:

ok 5000 tokens

Test #17:

score: 18
Accepted
time: 8ms
memory: 60700kb

input:

5000 5000
152 143 107 44 171 299 88 120 221 238 145 137 152 30 196 218 31 216 16 39 206 111 212 195 91 45 107 165 132 260 264 57 217 9 223 194 137 59 132 194 286 248 28 95 219 236 144 145 76 69 53 127 91 226 15 277 60 180 114 122 112 96 108 283 55 50 204 123 69 29 136 134 42 283 240 164 33 17 143 10...

output:

4076
2789
375
2375
2365
290
5779
1429
5357
1975
1146
4711
2438
4576
1984
173
4275
1748
1757
3292
538
495
3471
2870
1874
5565
2936
4736
1561
4658
6347
5936
1610
8726
518
3856
1264
2567
91
5371
4139
1415
6416
6198
4353
406
2055
7098
2759
1443
4707
4578
5778
6439
1210
353
2224
6103
4571
2885
4011
2550
...

result:

ok 5000 tokens

Test #18:

score: 18
Accepted
time: 4ms
memory: 60504kb

input:

5000 5000
7 4 1209 6 3 2 332 4 6 2 657 7 8 5 368 6 3 1 2973 4 1 2 1643 3 8 4 1694 4 7 2 1933 5 5 3 1973 5 3 6 1401 2 8 3 1040 6 4 3 2227 5 4 1 2731 3 4 5 352 5 4 5 2322 8 8 4 232 5 8 1 453 3 4 5 326 5 7 4 697 5 3 2 2147 6 8 8 1152 5 7 7 2473 2 8 1 2891 6 1 1 2272 5 1 6 2213 3 1 3 801 5 5 5 576 7 3 1...

output:

1018
12
2042
270
1610
1021
7798
4006
1210
5202
6022
2052
773
125
836
1197
776
3831
5968
1374
2347
5766
1114
775
1165
3509
3064
3466
358
1922
2690
5393
7095
7059
332
190
1891
465
4456
1433
290
1436
2757
1719
2419
381
3178
3840
4651
4306
2005
3381
5578
482
6578
956
370
3855
6519
730
61
403
2485
6281
4...

result:

ok 5000 tokens

Test #19:

score: 18
Accepted
time: 7ms
memory: 60856kb

input:

5000 5000
4 3 103 4 8 7 161 4 7 7 140 5 1 6 67 8 6 4 205 1 6 2 21 4 2 2 282 2 4 1 250 5 5 2 245 6 7 6 244 5 4 4 260 7 5 5 179 5 5 5 154 5 2 3 94 4 6 8 135 1 1 2 75 2 3 5 249 4 3 3 56 1 4 8 270 2 8 6 73 2 6 6 266 1 1 6 278 8 8 2 289 8 7 4 183 2 1 2 31 3 1 2 272 7 5 8 76 5 6 2 184 8 5 7 148 5 3 6 168 ...

output:

4424
2995
6615
3747
1334
2893
6258
435
1827
3526
4341
3901
171
208
1182
1643
6200
3004
6199
1423
539
2
454
3812
1875
1363
6700
46
3560
2469
2342
2394
463
3029
3029
553
2509
1466
617
1565
1793
2747
3712
2241
7207
1463
2596
5856
3070
184
7288
1260
2419
907
422
1314
326
4032
184
1558
2087
6776
1756
302...

result:

ok 5000 tokens

Test #20:

score: 18
Accepted
time: 11ms
memory: 59316kb

input:

5000 5000
6 2 14 6 7 2 17 6 8 4 13 6 6 2 22 1 4 2 3 3 5 1 27 3 4 8 3 6 1 3 23 5 2 8 2 3 4 3 26 4 1 2 18 3 6 2 9 6 1 2 24 8 7 1 26 8 3 1 29 1 6 6 12 5 6 4 11 1 3 3 11 5 5 7 22 5 4 8 30 6 7 3 11 1 4 3 19 3 2 3 21 2 1 2 14 4 3 1 24 6 5 3 30 3 8 8 18 6 1 6 24 3 4 2 3 7 2 6 28 2 7 2 7 1 5 6 16 4 6 7 26 8...

output:

1240
1101
1137
781
3879
1962
1076
4946
4640
3529
6246
4952
3530
1154
2204
1476
2062
3967
8274
1572
7066
5945
6119
1876
7651
1168
5715
209
1021
4649
99
2534
3981
1358
1795
2442
1020
3338
743
3595
7592
60
533
873
4665
4269
2977
2464
1905
3465
769
5539
1670
1383
4200
475
730
7285
4782
727
99
1386
2090
...

result:

ok 5000 tokens

Test #21:

score: 18
Accepted
time: 10ms
memory: 60592kb

input:

5000 5000
7 65 24 32 64 13 57 54 44 52 28 17 54 54 9 1 33 50 52 18 52 54 45 65 52 39 10 16 16 27 58 65 18 16 7 1 58 2 32 52 15 64 50 1 56 26 21 45 26 22 35 9 46 46 22 35 20 55 22 22 13 35 15 36 50 14 33 35 15 24 34 29 12 53 50 12 12 22 64 63 64 6 56 53 54 63 41 30 18 42 31 32 25 37 7 38 13 65 53 65 ...

output:

1230
4538
1060
773
5338
1664
5664
1384
1654
4698
1040
1915
833
5362
4999
2164
3743
848
7227
3954
5554
2048
4136
3807
1076
4985
3268
2288
816
2789
5537
8357
5496
5868
3758
5801
4432
1620
1701
743
2216
21
6265
750
4262
471
20
4135
2147
6773
4229
1672
4850
2643
3572
5759
3160
6
3773
5899
2392
898
1715
...

result:

ok 5000 tokens

Test #22:

score: 18
Accepted
time: 8ms
memory: 60872kb

input:

5000 5000
66 49 61 50 10 54 16 40 35 51 36 53 28 42 12 9 1 21 64 39 61 2 14 6 26 59 40 47 45 55 40 9 51 44 59 32 64 12 65 51 51 13 58 45 50 30 59 28 22 50 44 3 31 61 30 59 20 17 4 29 26 21 1 32 61 51 63 4 12 35 63 10 21 10 60 29 21 55 40 44 13 25 46 9 23 12 40 21 56 41 11 20 16 47 23 39 49 13 46 56 ...

output:

1911
6540
1235
1742
1887
2967
222
3250
8800
6308
1452
2418
2200
2866
125
507
1217
1632
2255
1729
5348
3099
6724
2097
2300
1169
919
1713
2468
3723
5396
3511
60
5701
974
1085
3788
6593
7875
3496
444
2551
1547
1190
6668
2274
5407
920
3249
2251
3898
873
2745
2259
2497
288
1913
2858
4429
4723
1317
1000
6...

result:

ok 5000 tokens

Subtask #4:

score: 66
Accepted

Test #23:

score: 66
Accepted
time: 419ms
memory: 101184kb

input:

1000000 1000000
1105 3246 1880 3554 818 2331 2576 4140 149 4562 3498 3536 3400 4788 4363 4742 1216 4218 4032 1701 1489 4889 1761 3022 3145 4945 3067 4304 5016 4624 1612 13 1335 3613 1086 2210 386 3464 1156 3352 4341 5006 3465 3900 622 654 1826 2983 1250 4164 3335 4308 2995 1982 1347 4335 2535 5054 4...

output:

1263815
308608
760115
79452
160350
576908
988222
1716103
1345118
215185
615960
546263
1385912
320711
1094276
52291
276158
227555
2476
147750
144806
667128
25418
223778
184324
1445226
1666310
547639
146406
969316
1106498
237554
817297
112491
84810
1188701
316694
717959
169528
559867
767792
412202
732...

result:

ok 1000000 tokens

Test #24:

score: 66
Accepted
time: 451ms
memory: 100728kb

input:

1000000 1000000
527 3920 401 1486 606 3642 1277 2668 2579 2728 4669 3313 730 4241 3197 841 2036 2758 2687 4946 1352 15 3445 1010 2485 2764 2501 1864 4501 3756 3605 3685 543 4866 4450 3713 4592 3814 243 1778 4446 18 3845 4874 726 665 532 345 1419 4381 107 3763 4941 2 280 759 4744 3537 4146 4289 4426 ...

output:

1266412
85167
6797
467075
143942
401875
230600
686422
136253
620827
383202
16007
507791
208181
160399
1625926
143357
1304506
472925
24772
854987
1424226
204580
1217006
632808
872879
94028
64186
1444974
66982
13649
728491
882172
340172
1228584
975111
1172671
745171
885348
894087
1107690
268570
466233...

result:

ok 1000000 tokens

Test #25:

score: 66
Accepted
time: 322ms
memory: 100100kb

input:

1000000 1000000
2924 2207 2863 3688 4354 2178 249 3641 1722 832 2166 2993 4965 1712 467 2985 3155 2499 3697 2198 418 3206 3363 4939 3519 2498 208 2350 1915 883 1304 1289 1176 2940 2528 2265 3205 309 5027 3131 1605 823 2063 1070 1933 1098 3623 3306 3752 1371 2204 3170 3931 773 4029 518 4930 4632 3123...

output:

66552
421925
47840
553007
101473
741226
342901
905017
1128131
262875
916454
1271725
1687005
549894
461128
99677
1076946
1396038
873472
839214
231408
1136724
594832
634884
985318
1069765
157496
353491
1831090
347730
1238853
1340386
433279
1226192
59056
453400
381770
407755
4657
477432
990073
345545
3...

result:

ok 1000000 tokens

Test #26:

score: 66
Accepted
time: 393ms
memory: 105400kb

input:

1000000 1000000
5 16 21 17 3 10 7 15 6 9 22 21 23 17 13 6 2 2 23 15 21 14 8 5 14 1 5 12 20 12 18 6 8 13 11 4 19 6 18 10 14 16 16 7 10 2 10 7 17 7 4 16 3 6 5 19 18 12 9 21 3 6 23 20 1 12 14 16 11 4 9 18 23 6 20 21 15 11 19 10 15 17 12 4 16 18 16 6 4 11 18 6 19 3 11 20 19 18 4 12 20 15 18 19 15 23 13 ...

output:

294395
420853
822090
194055
532781
964093
947612
736480
1446204
88624
134267
352128
464091
701123
539319
935940
599255
145934
836926
828952
1085534
1344842
40896
80662
113493
159050
1049192
1714818
1320340
81557
625083
53129
288299
407143
839047
608795
1283945
840785
754964
30413
508507
595737
44664...

result:

ok 1000000 tokens

Test #27:

score: 66
Accepted
time: 495ms
memory: 106120kb

input:

1000000 1000000
1 6 223557 1 7 4 127763 7 4 4 80635 3 1 3 53028 1 1 2 84986 1 8 2 27125 4 7 4 27663 3 4 4 215521 3 3 5 133609 1 3 1 8988 1 2 1 218287 1 3 7 103225 8 6 6 24843 6 4 4 216981 3 7 8 115404 1 3 2 46715 2 6 6 223678 6 2 7 236459 5 5 2 53633 7 1 5 235534 2 6 5 19831 7 2 1 215142 7 5 8 24037...

output:

357045
786579
143090
1373069
172510
758982
449417
77391
511138
213308
995151
980951
203253
351187
153758
377750
127440
90886
219002
980485
39540
886637
1141408
783311
1300939
868805
54983
1149265
208525
847343
464980
514460
41821
919043
317204
1234867
179994
1542388
200511
277798
808340
1208174
8866...

result:

ok 1000000 tokens

Test #28:

score: 66
Accepted
time: 433ms
memory: 105968kb

input:

1000000 1000000
3 2478 2 2515 2 615 1 2351 2 2545 2 52 1 1388 3 1840 3 931 1 2081 2 935 1 600 3 332 2 1249 3 740 3 96 2 1828 2 2265 2 634 2 720 2 1279 1 1208 3 1289 3 2549 1 725 3 1940 2 484 1 2317 1 1474 3 1193 3 655 2 2043 2 2175 3 2087 1 1117 1 1629 3 1999 3 2359 1 2020 3 2054 3 2018 3 1473 2 496...

output:

600467
959248
541839
228808
654539
316217
511900
930379
439623
493921
104805
816096
494134
525285
10249
177901
567592
582869
651865
1066756
708338
218409
184719
59172
466928
692702
874942
182105
215210
588082
839888
313230
524603
271923
745012
776906
109219
994839
991791
3849
872457
1138687
381796
1...

result:

ok 1000000 tokens

Test #29:

score: 66
Accepted
time: 187ms
memory: 92772kb

input:

1000000 1000000
379981 742013 610531 254482 462859 798729 207070 822658 302999 774930 162638 338078 984726 93312 153637 696061 367310 995629 205637 236915 751467 354098 987526 678853 311408 986720 533832 988116 790040 535482 973118 312417 163050 810868 359919 65418 513554 592094 904848 879499 261172...

output:

1998214
1997879
1997187
1997693
1996147
1998130
1998172
1995769
1997990
1997051
1996637
1997384
1997077
1998664
1998464
1996681
1998268
1997187
1998186
1996779
1997752
1997011
1996607
1998790
1996789
1997452
1997871
1998756
1998838
1997447
1997795
1996573
1996741
1997673
1997159
1998592
1997573
1997...

result:

ok 1000000 tokens

Test #30:

score: 66
Accepted
time: 228ms
memory: 93600kb

input:

1000000 1000000
616046 27 466646 59 202679 5 488319 13 18291 48 561757 98 143729 8 600006 41 695086 41 365757 22 635169 74 471529 88 381867 78 722475 80 827042 12 421497 64 808590 78 679513 70 652788 38 726970 29 611209 14 225100 66 43003 68 271236 85 524862 89 718307 60 198067 82 34292 43 714269 3 ...

output:

1956922
1956697
1956551
1957457
1956554
1956573
1957964
1957906
1958240
1956083
1957673
1957009
1958503
1958002
1956898
1956535
1956347
1955623
1956114
1955034
1956194
1957633
1955930
1957226
1956584
1956614
1956319
1956788
1958012
1957835
1955592
1958033
1956138
1957476
1957103
1958462
1956496
1957...

result:

ok 1000000 tokens