QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198408#7437. 博丽灵梦zhouhuanyi100 ✓6087ms35648kbC++234.6kb2023-10-03 13:41:482023-10-03 13:41:49

Judging History

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

  • [2023-10-03 13:41:49]
  • 评测
  • 测评结果:100
  • 用时:6087ms
  • 内存:35648kb
  • [2023-10-03 13:41:48]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100001
#define M 1000000
#define K 350
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,m,r,sz,szt,szt2,num[N+1],num2[N+1],p[N+1],q[N+1],a[N+1],lst[N+1],block[N+1],blocks[N+1],blocks2[N+1],blocks3[N+1],ft[K+1],ed[K+1],ft2[K+1],ed2[K+1],pv[N+1],nt[N+1];
unsigned int tans,delta[N+1],delta2[N+1],b[N+1],A[K+1][K+1],B[K+1][K+1],C[K+1][K+1],D[K+1][K+1],E[N+1],F[K+1],G[N+1],H[K+1],ans[M+1];
struct reads
{
	int l1,r1,l2,r2,num;
	bool operator < (const reads &t)const
	{
		return block[l1]!=block[t.l1]?block[l1]<block[t.l1]:r1>t.r1;	
	}
};
reads st[M+1];
inline void adder(int l,int r,unsigned int ds,int d)
{
	if (l==1)
	{
		E[r]+=ds,F[blocks3[r]]+=ds;
		return;
	}
	if (r==n)
	{
		G[l]+=ds,H[blocks3[l]]+=ds;
		return;
	}
	if (d==1) num[l]=r,num2[r]=l,delta[l]=delta2[r]=ds;
	else num[l]=delta[l]=num2[r]=delta2[r]=0;
	A[blocks[l]][blocks[r]]+=ds,B[blocks[l]][blocks2[r]]+=ds,C[blocks2[l]][blocks[r]]+=ds,D[blocks2[l]][blocks2[r]]+=ds;
	return;
}
unsigned int query(int l,int r)
{
	unsigned int res=0;
	for (int i=r;i<=min(blocks3[r]*szt2,n);++i) res+=E[i];
	for (int i=blocks3[r]+1;i<=blocks3[n];++i) res+=F[i];
	for (int i=(blocks3[l]-1)*szt2+1;i<=l;++i) res+=G[i];
	for (int i=1;i<=blocks3[l]-1;++i) res+=H[i];
	for (int i=1;i<=blocks[l]-1;++i)
	{
		for (int j=blocks[r]+1;j<=blocks[n];++j) res+=A[i][j];
		for (int j=blocks2[r]+1;j<=ed[blocks[r]];++j) res+=B[i][j];
	}
	for (int i=ft[blocks[l]];i<=blocks2[l]-1;++i)
	{
		for (int j=blocks[r]+1;j<=blocks[n];++j) res+=C[i][j];
		for (int j=blocks2[r]+1;j<=ed[blocks[r]];++j) res+=D[i][j];
	}
	for (int i=ft2[blocks2[l]];i<=l;++i)
		if (num[i]&&num[i]>=r)
			res+=delta[i];
	for (int i=r;i<=ed2[blocks2[r]];++i)
		if (num2[i]&&num2[i]<=ft2[blocks2[l]]-1)
			res+=delta2[i];
	return res;
}
int main()
{
    int s1,s2;
	n=read();
	for (int i=1;i<=n;++i) p[i]=read(),q[p[i]]=i;
	for (int i=1;i<=n;++i) a[i]=read();
	for (int i=1;i<=n;++i) b[i]=read(),tans+=b[i];
	m=read();
	for (int i=1;i<=m;++i) st[i].l1=read(),st[i].r1=read(),st[i].l2=read(),st[i].r2=read(),st[i].num=i;
	sz=max((int)(n/max((int)(sqrt(m)),1)),1),szt=max((int)(pow(n,0.75)),1),szt2=max((int)(sqrt(n)),1);
	for (int i=1;i<=n;++i) block[i]=(i-1)/sz+1,blocks[i]=(i-1)/szt+1,blocks3[i]=(i-1)/szt2+1;
	for (int i=1;i<=blocks[n];++i)
	{
		blocks2[(i-1)*szt+1]=blocks2[(i-1)*szt]+1;
		for (int j=(i-1)*szt+1;j<=min(i*szt,n)-1;++j) blocks2[j+1]=blocks2[j]+((j-(i-1)*szt)%szt2==0);
	}
	for (int i=1;i<=blocks[n];++i) ft[i]=blocks2[(i-1)*szt+1],ed[i]=blocks2[min(i*szt,n)];
	for (int i=1;i<=n;++i)
	{
		if (!ft2[blocks2[i]]) ft2[blocks2[i]]=i;
		ed2[blocks2[i]]=i;
	}
	sort(st+1,st+m+1);
	for (int i=1;i<=m;++i)
	{
		if (block[st[i].l1]!=block[st[i-1].l1])
		{
			for (int j=1;j<=n;++j) lst[j]=pv[j]=num[j]=delta[j]=num2[j]=delta2[j]=0,nt[j]=n+1;
			for (int j=1;j<=K;++j)
				for (int t=1;t<=K;++t)
					A[j][t]=B[j][t]=C[j][t]=D[j][t]=0;
			for (int j=1;j<=n;++j) E[j]=G[j]=0;
			for (int j=1;j<=K;++j) F[j]=H[j]=0;
			for (int j=1;j<=n;++j)
				if ((block[st[i].l1]-1)*sz+1<=q[j]&&q[j]<=st[i].r1)
					pv[j]=lst[a[q[j]]],lst[a[q[j]]]=j;
			for (int j=1;j<=n;++j) lst[j]=n+1;
			for (int j=n;j>=1;--j)
				if ((block[st[i].l1]-1)*sz+1<=q[j]&&q[j]<=st[i].r1)
					nt[j]=lst[a[q[j]]],lst[a[q[j]]]=j;
			for (int j=1;j<=n;++j)
				if ((block[st[i].l1]-1)*sz+1<=q[j]&&q[j]<=st[i].r1)
				{
					if (pv[j]+1<=j-1) adder(pv[j]+1,j-1,b[a[q[j]]],1);
					if (nt[j]==n+1&&j+1<=n) adder(j+1,n,b[a[q[j]]],1);
				}
			for (int j=1;j<=n;++j)
				if (lst[j]==n+1)
					adder(1,n,b[j],1);
			r=st[i].r1;
		}
		while (r>st[i].r1)
		{
			s1=pv[p[r]],s2=nt[p[r]];
			if (s1+1<=p[r]-1) adder(s1+1,p[r]-1,-b[a[r]],-1);
			if (p[r]+1<=s2-1) adder(p[r]+1,s2-1,-b[a[r]],-1);
			if (s1+1<=s2-1) adder(s1+1,s2-1,b[a[r]],1);
			nt[s1]=s2,pv[s2]=s1,r--;
		}
		for (int j=(block[st[i].l1]-1)*sz+1;j<=st[i].l1-1;++j)
		{
			s1=pv[p[j]],s2=nt[p[j]];
			if (s1+1<=p[j]-1) adder(s1+1,p[j]-1,-b[a[j]],-1);
			if (p[j]+1<=s2-1) adder(p[j]+1,s2-1,-b[a[j]],-1);
			if (s1+1<=s2-1) adder(s1+1,s2-1,b[a[j]],1);
			nt[s1]=s2,pv[s2]=s1;
		}
		ans[st[i].num]=tans-query(st[i].l2,st[i].r2);
		for (int j=st[i].l1-1;j>=(block[st[i].l1]-1)*sz+1;--j)
		{
			s1=pv[p[j]],s2=nt[p[j]];
			if (s1+1<=s2-1) adder(s1+1,s2-1,-b[a[j]],-1);
			if (s1+1<=p[j]-1) adder(s1+1,p[j]-1,b[a[j]],1);
			if (p[j]+1<=s2-1) adder(p[j]+1,s2-1,b[a[j]],1);
			nt[s1]=pv[s2]=p[j];
		}
	}
	for (int i=1;i<=m;++i) printf("%u\n",ans[i]);
	return 0;
}

详细

Test #1:

score: 4
Accepted
time: 0ms
memory: 13868kb

input:

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

output:

6
24
9
9
0
9
20
9
18
0

result:

ok 10 numbers

Test #2:

score: 4
Accepted
time: 22ms
memory: 14120kb

input:

5000
4584 3973 1352 4671 419 4060 2422 1887 1113 4149 3583 511 2168 3996 963 870 1871 1972 2974 3771 2725 2276 4578 194 4600 114 4297 1714 3530 3353 2904 4842 366 744 116 1785 3646 2473 1421 4245 1366 4483 1555 4595 1179 1394 3648 3066 4024 1935 2263 4237 4268 29 2148 4647 4515 2135 4131 4589 3314 2...

output:

327117
136689
1479698
1136737
449729
1711409
450967
763623
858017
807158
284267
1975776
1648557
1531841
417402
1109352
779487
3606
5497
491686
1800425
252458
96255
3426670
106777
1457932
21547
717391
1449681
334971
2332339
1508267
169612
3687559
347639
28409
388782
363513
244140
1945694
116465
67408...

result:

ok 5000 numbers

Test #3:

score: 4
Accepted
time: 222ms
memory: 16616kb

input:

25000
17933 12647 4126 561 20565 17721 3237 20956 23810 15182 1371 1964 19155 23873 16313 20143 23077 15413 14837 23101 15220 2217 22784 2221 17865 11528 9072 23426 15666 9562 23566 7278 11913 6636 10360 8741 13378 13274 515 17382 15017 11838 24731 10977 643 23193 24811 18852 20273 17879 16016 2687 ...

output:

44331710
96283081
87530730
38741823
58043413
55254246
67615705
37985774
22050584
103215771
59813290
96181328
30218492
87030588
64939548
95314170
26427029
89913865
13923644
53206182
85913027
77294146
12276632
82340332
33993445
88588245
72575496
73838518
52753249
34970184
88425783
51570715
90607205
10...

result:

ok 50000 numbers

Test #4:

score: 4
Accepted
time: 676ms
memory: 21204kb

input:

50000
34190 30883 11333 45339 39327 7782 31720 17826 49088 48395 26423 1963 15006 13296 31887 39411 41575 47505 26979 39758 29082 5053 35619 36746 28511 45672 37295 30506 46420 36833 48283 34088 32552 48561 22638 32469 22093 49328 21194 8280 24202 26909 49400 11332 12274 29937 15451 42485 48625 4052...

output:

227264514
53888707
209222883
335000290
92884912
401778242
412584678
226832518
48811424
19033298
192106617
347861035
138441583
32850600
254270587
227957491
160579318
409756013
354290805
117176339
232829675
410617733
412919632
314673122
169514751
310233166
355456068
290623572
384996342
323750695
75291...

result:

ok 100000 numbers

Test #5:

score: 4
Accepted
time: 1451ms
memory: 18976kb

input:

75000
30149 54180 3798 34212 67897 28067 50060 44816 38037 27530 70405 68069 16326 14256 66092 36541 72536 72996 63812 65847 23781 72137 39834 29700 11212 11156 41911 9140 57560 21211 39159 53063 71051 45303 39914 9566 32134 69835 24071 7055 58777 70053 69284 73900 53302 28963 74142 46429 7921 57247...

output:

498247291
125087749
288284686
545291282
318837027
478497408
267105309
241459794
623291564
277490499
428871457
261509795
602407456
218421901
33089111
103723445
133469666
213316994
171193580
76404390
398799418
596192023
185406527
526946854
542083913
198980307
158885211
600895050
555518622
336629815
30...

result:

ok 150000 numbers

Test #6:

score: 4
Accepted
time: 2352ms
memory: 19200kb

input:

100000
47534 82358 90198 90311 86971 78138 57685 92820 95572 82397 45779 74859 67319 89881 76297 71344 68227 55217 75262 94126 96422 87581 94223 87931 88679 42475 75545 30649 91491 96694 85088 94656 24494 69871 78199 69331 99352 18668 74574 78408 79693 61591 99297 49169 83870 93128 88383 69981 66151...

output:

786293990
809741070
830957031
510917218
370399323
509692992
769450484
62293955
157004479
455061060
198854004
429141104
735611184
754768000
790444094
811507828
635857494
756277771
228330537
429761575
681154948
86673390
60203242
820444772
102645520
752520001
788753355
810206783
107140606
835476467
822...

result:

ok 200000 numbers

Test #7:

score: 4
Accepted
time: 114ms
memory: 16168kb

input:

20000
11616 14681 9191 15174 9118 13157 14663 13691 19020 4289 1661 17151 11530 10198 10148 7691 1626 8200 5742 16570 17497 342 19688 4812 9998 16500 8667 16256 16815 5543 2734 13845 2182 8140 17207 15824 4253 474 9157 8209 14695 6161 8064 19843 1130 13147 19730 10224 7634 12957 14900 7442 11608 138...

output:

2016662
6773498
16534227
7264977
8255967
20382699
8614253
36830556
6684778
1707073
21596412
32682670
6404798
13544211
3015074
32926912
2438256
13675665
23244560
116740
12652456
3120774
26092
35826021
5516953
580396
46007357
16163011
3231113
8955441
12216687
1402777
21395122
130204
10097522
31481510
...

result:

ok 19260 numbers

Test #8:

score: 4
Accepted
time: 320ms
memory: 19096kb

input:

30000
18100 17984 29616 26532 16351 25306 28940 17968 12149 21623 10913 25728 7504 1694 18649 20697 12374 28510 28482 24090 23186 26948 24342 8516 28375 24474 26716 10580 18582 25290 29675 5255 22335 21818 28936 918 11068 8231 14805 25816 29904 26304 12336 12440 28867 27898 20999 18451 17788 10485 2...

output:

57833084
14731524
7903237
111647773
4838310
59648591
10688753
50939852
5221720
113380726
24782301
22498185
61111304
39389586
37258737
9093606
25185482
84788372
6132515
28307612
54940963
56002962
72959218
2090556
131394639
13444906
3911685
36151408
11946266
42502314
9084655
3594198
7500469
6076377
48...

result:

ok 60000 numbers

Test #9:

score: 4
Accepted
time: 512ms
memory: 19056kb

input:

40000
6155 33310 18982 32436 23117 11936 23625 36826 24896 18185 2373 31232 5057 20465 18997 36213 39297 32273 32461 29674 18962 13728 30106 33069 4625 35639 28937 32955 36807 31210 12487 33040 26415 13758 38447 20070 16135 32305 34756 22396 24672 32400 28184 22671 5895 5628 7054 27520 28612 17575 2...

output:

59904501
70143888
59811293
195743836
1744154
25195482
57604334
117819987
34994132
36249031
52417701
50111583
9647642
23383074
42774621
19096838
22573471
50267641
1589526
9086793
189945645
221200860
66439930
491745
26978686
195833990
156144513
28473299
6741170
126902399
15066387
62835888
86603659
635...

result:

ok 80000 numbers

Test #10:

score: 4
Accepted
time: 715ms
memory: 16364kb

input:

50000
38469 24525 32217 24789 47311 24293 3571 14829 26717 913 21309 8308 37327 8734 17912 43870 48997 10733 2270 26728 7330 16464 40796 11288 47560 48672 46090 18389 25933 46137 41744 48976 38039 41118 38084 40612 47921 45345 45410 48851 31754 38299 27413 23608 24009 31513 40500 49878 8252 41404 10...

output:

148215047
0
216986318
5831
16783
126583183
0
0
34124
81218014
16106222
54161780
63692945
166125144
161529422
0
127413844
11007965
5814593
17627268
130633805
14058
178027524
37209907
377062004
299851077
16357888
18056649
67967647
127722722
129397643
54710309
64255672
304034543
19890218
17840078
11460...

result:

ok 100000 numbers

Test #11:

score: 4
Accepted
time: 1027ms
memory: 18800kb

input:

60000
28929 27272 6259 45423 15780 40321 15580 4868 47291 3546 27936 45710 20567 26606 30216 52113 50838 55739 49818 56542 31288 49488 50806 8957 57695 52604 58066 14076 38002 58344 26180 36232 22180 32879 34138 51711 34760 25593 43389 31396 51616 13814 58547 40038 55058 48403 34408 25186 51758 5163...

output:

244276857
0
284344283
0
0
146084507
0
0
1668
106818381
8968278
44854864
104083176
203074976
235916858
17954059
146513450
224501114
20607551
16147239
186157015
0
804258
23852222
454150729
115599586
16873150
8051384
98976732
197057650
134859306
73023326
133491334
164378248
27429206
31934670
55268105
2...

result:

ok 120000 numbers

Test #12:

score: 4
Accepted
time: 1369ms
memory: 18796kb

input:

70000
52924 17320 66317 8157 30299 14111 65609 39835 21071 62191 51780 53198 44998 54574 66213 14371 58818 68483 39851 47765 42611 69393 63471 60519 9205 11577 69131 61430 13885 29809 66714 44006 62051 58921 12599 53974 40692 64816 36682 3519 24905 52640 10114 68493 49109 41844 48600 66776 38530 433...

output:

0
353884553
0
44095
140023351
20361
0
872
150061948
731732
44269748
180474939
270273912
318884383
22089937
198606953
20427413
46389031
11746813
238821828
98808
521275873
34460069
527377772
264680230
20991160
0
123677882
278780630
140643482
78560730
134973093
160597952
18374781
320907495
132400957
18...

result:

ok 140000 numbers

Test #13:

score: 4
Accepted
time: 1282ms
memory: 19268kb

input:

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 99 100 1...

output:

0
541365899
0
0
509012400
199252651
0
128799486
797139558
19463720
477678233
390832483
0
40142895
0
0
0
524716553
192736264
826258298
364300815
0
11786890
725130075
0
0
0
100234984
603217331
0
157526958
185807221
0
0
197527131
400524242
0
178428721
0
11758986
279481496
18298387
7313717
0
0
0
4637891...

result:

ok 200000 numbers

Test #14:

score: 4
Accepted
time: 1286ms
memory: 23360kb

input:

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 99 100 1...

output:

340948192
666834767
491129420
123074590
628648083
82578767
440168007
0
818378946
0
715595527
164282503
0
426712669
282614797
341292996
0
233273733
0
767288817
216436396
304576216
0
672382672
0
547502846
609414492
44228592
701325703
0
631426804
0
0
391026022
384188945
0
725862111
0
64868662
657746274...

result:

ok 200000 numbers

Test #15:

score: 4
Accepted
time: 1292ms
memory: 23360kb

input:

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 99 100 1...

output:

55356
0
800875150
47778
0
471761412
142219
30193
0
0
0
417342124
0
652696020
111577391
0
661831114
37551804
47185388
0
407889806
57249
818793420
75271427
818100982
752383248
0
0
361206456
705016003
278071749
0
0
265178251
0
0
0
0
0
512825448
239691567
96100
592287991
233659585
196248877
654582194
82...

result:

ok 200000 numbers

Test #16:

score: 4
Accepted
time: 2317ms
memory: 21216kb

input:

95000
54869 89685 84021 77335 29643 94178 67158 60183 31735 63706 79776 89995 89643 62925 35391 76241 81318 59689 94539 42088 29258 71464 41104 76091 24922 72978 89700 92047 64960 12525 70519 82967 85527 88068 85048 89273 19561 66101 53150 88863 43065 94970 41214 71260 82429 52175 75847 14693 94497 ...

output:

688866
357090120
623261240
456747173
411632768
137302753
396561917
755731295
56748116
46703649
16272979
12037446
317311742
534699231
72638390
36658660
599493651
245054751
623734863
424526
346883607
89483999
371838621
30367525
132710
9394020
58537138
459621705
706511038
62430081
481109051
36214148
17...

result:

ok 190000 numbers

Test #17:

score: 4
Accepted
time: 2489ms
memory: 19184kb

input:

100000
85963 54232 81192 62832 86584 80503 31766 74547 68821 73102 73096 72267 89495 33829 99520 43962 54837 89342 84555 71099 98465 64321 69793 39525 70934 87510 76927 85543 80068 25394 93361 4064 75959 51666 98914 15652 80946 90768 98387 88616 95082 44075 76628 84428 90891 63623 85280 43215 12888 ...

output:

195238536
0
847172791
246643823
41640038
776282908
0
190374
465362560
162705118
0
367030500
684589630
44003
0
0
61570265
324013704
530946210
176533774
27643435
284652614
155290218
210218733
226106228
33576123
230854966
55280998
22072112
441003919
3660246
118713173
0
210487126
684826374
72979474
1066...

result:

ok 200000 numbers

Test #18:

score: 4
Accepted
time: 2479ms
memory: 23348kb

input:

100000
90787 49393 38459 68555 92570 80827 83843 39871 57205 59948 85227 96519 94578 78479 78947 89776 58887 21176 89863 99298 44414 29776 25867 88717 53798 75196 76719 87201 71049 86356 44186 47657 77140 74621 90681 81634 99004 97417 67801 73807 30440 47271 98457 50945 68642 92999 98340 99414 14611...

output:

0
0
785519681
0
18194
161923912
141141868
280337095
46101
805032446
0
215852977
197568121
10100833
257064479
58803
348427599
0
88703
647208328
289605684
23731
300021601
42843195
88154776
809377761
4612537
0
162648410
560299893
85015902
58803
65147337
208775716
0
0
272351727
112748915
130611083
20071...

result:

ok 200000 numbers

Test #19:

score: 4
Accepted
time: 3300ms
memory: 25560kb

input:

100000
56193 78732 53570 44033 95995 99805 99585 94328 86681 87057 38285 74770 35856 6475 67612 52118 61883 18643 94607 31187 29338 88506 19752 84313 95851 96938 75747 72293 99364 67597 58337 99189 57651 74675 88241 44625 85781 27224 95532 74927 99055 98502 50279 27215 87270 20715 81841 89907 89718 ...

output:

14061144
101989697
27600218
141316308
7552530
43379441
110653815
226090615
1184187
117129619
231117085
8168491
47944934
20720844
260488561
52769282
85101694
56155984
373137463
223954743
5315378
39211425
114594035
425744039
167972336
68649020
338398079
353672952
194901191
5415300
2763525
0
40926220
2...

result:

ok 300000 numbers

Test #20:

score: 4
Accepted
time: 3836ms
memory: 25560kb

input:

100000
54722 84563 96554 77985 99277 67108 96381 71428 89162 91934 89671 74392 31632 30282 14966 88796 75550 96930 3617 82001 88145 28169 71044 85311 22416 30942 30195 99275 88970 30785 61892 84018 48484 19580 65559 90924 92214 43453 76013 9855 77640 76849 60741 31437 99618 3508 5054 87130 26889 946...

output:

191231349
83924764
4958504
14936002
176052477
3208631
0
278976252
0
12498033
159933379
34172998
165668822
7388541
138973697
125881447
80661624
17664149
221056918
35759428
164320952
271736521
14280348
348694858
54682121
4329351
194541803
376424800
257264997
8303563
9206118
81291286
428629996
82354424...

result:

ok 400000 numbers

Test #21:

score: 4
Accepted
time: 3933ms
memory: 27612kb

input:

100000
69536 76666 30096 75927 68899 60112 50144 27911 91674 77923 64608 95868 89728 87803 87234 62536 90788 95452 75434 48468 83595 97682 61133 69084 86299 99064 81737 90986 94384 95563 96802 37554 83608 94954 80895 23078 92537 56143 80659 14842 93617 92962 91436 39232 97232 67436 98527 67131 73774...

output:

288529716
50920967
470998875
77430934
32828426
24104869
483483409
361252584
58199482
896170383
26460839
342703961
664356685
510328540
687791838
619270702
963056570
333695658
486475685
694644099
520058242
218107010
183952685
167237061
79351600
120763457
309222699
108935295
28375287
41891239
98425903
...

result:

ok 500000 numbers

Test #22:

score: 4
Accepted
time: 4577ms
memory: 29436kb

input:

100000
25377 81949 73151 50640 84530 48045 12139 82295 59977 92190 83405 82243 94236 93605 83319 98058 89610 91310 38547 86841 81877 90240 70172 35462 69666 93781 81392 54806 87407 99453 99244 58440 95573 88739 5938 84504 56614 23803 77556 47383 87088 73684 82110 83163 35349 92668 73141 20736 70294 ...

output:

72320976
7143666
69656921
16916127
370374695
3181879
424925985
121370165
2325982
17026352
326868148
0
28830907
28177824
363089202
675262846
405062312
251088115
387300794
253372604
1059792
493827606
40274110
185746174
4136822
24503795
165622618
322320991
9086004
16104752
1426847
411147551
286890153
3...

result:

ok 600000 numbers

Test #23:

score: 4
Accepted
time: 5284ms
memory: 33600kb

input:

100000
68911 78955 67125 63739 77253 93872 98284 30234 65137 93114 55561 50049 18255 97663 75460 27811 96088 82376 74231 62398 67493 59605 51358 41605 88345 83081 83446 37670 52929 59276 32521 95748 30602 11042 62878 97612 83929 41373 30569 82057 79198 90481 19440 97993 30901 96818 84076 87404 9354 ...

output:

482253646
119800632
277099161
506686512
60820284
245908318
352333100
122773088
324430978
515824666
76816226
30727551
6963070
80491747
1314672
0
500069618
354796639
138107533
2516581
188860347
23760632
220691024
74062583
8782390
146785996
26094237
45950279
194908497
467189335
25756747
62419870
224188...

result:

ok 800000 numbers

Test #24:

score: 4
Accepted
time: 6087ms
memory: 35648kb

input:

100000
38458 39973 76990 86656 70315 70763 69153 94522 73043 96732 91705 43575 10537 63472 87305 65815 77792 96549 40795 68033 60805 57972 92038 84405 83637 18269 75531 94024 85636 83976 61301 74283 59778 5838 70252 73510 86230 62884 52089 84610 88915 78999 96146 35458 90912 98152 93863 35686 99939 ...

output:

97544675
65926466
2409685
84020551
236403697
23337442
145414590
41442071
3829154
546255
93905026
98370661
129557570
642911408
25627427
480410036
18617228
70411556
419076497
11466343
20678798
116287734
86651486
10645174
7392384
23330536
259679516
44157263
505062100
32920070
47446197
87107442
40167569...

result:

ok 1000000 numbers

Test #25:

score: 4
Accepted
time: 6061ms
memory: 35504kb

input:

100000
17357 75572 76084 97973 70590 40014 38940 43780 66344 53972 29698 53880 32667 26551 87331 3607 91253 63177 86190 42335 94989 38370 32515 59279 35119 38533 93007 8473 46782 85420 98270 27516 83838 66639 57364 91913 46439 83749 30263 97990 18522 97105 87000 80718 98885 29744 95730 93844 98301 2...

output:

130028069
0
678550282
183826223
33107759
627167873
8257
34405
315815529
131958077
0
403770734
573675437
0
14085
87685
40557657
243098285
459197631
127016294
28590434
275126478
154540376
194379542
157403650
5862700
233113692
61084989
24985932
337173311
5516642
83671483
0
154668161
526542469
62781750
...

result:

ok 1000000 numbers