QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422497#8084. AlakazamAfterlife#AC ✓332ms19704kbC++171.5kb2024-05-27 15:16:482024-05-27 15:16:49

Judging History

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

  • [2024-05-27 15:16:49]
  • 评测
  • 测评结果:AC
  • 用时:332ms
  • 内存:19704kb
  • [2024-05-27 15:16:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+1e3+7;

struct T{
	int l,r,ls,rs;
	double tag,sum;
}t[N*2+1];

int cnt;

void update(int x)
{
	t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
}

void setv(int x,double v)
{
	t[x].tag=v;
	t[x].sum=(t[x].r-t[x].l+1)*v;
}

void pushdown(int x)
{
	if(t[x].tag>0)
	{
		setv(t[x].ls,t[x].tag);
		setv(t[x].rs,t[x].tag);
		t[x].tag=-1;
	}
}

int build(int l,int r)
{
	int x=++cnt;
	t[x].l=l,t[x].r=r;
	t[x].tag=-1;
	if(l==r)
	{
		int V;
		cin>>V;
		t[x].sum=V;
		return x;
	}
	int mid=(l+r)>>1;
	t[x].ls=build(l,mid);
	t[x].rs=build(mid+1,r);
	update(x);
	return x;
}

void change(int x,int l,int r,double v)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		setv(x,v);
		return;
	}
	pushdown(x);
	int mid=(t[x].l+t[x].r)>>1;
	if(l<=mid)
		change(t[x].ls,l,r,v);
	if(r>mid)
		change(t[x].rs,l,r,v);
	update(x);
}

double qry(int x,int l,int r)
{
	if(l<=t[x].l&&t[x].r<=r)
		return t[x].sum;
	pushdown(x);
	int mid=(t[x].l+t[x].r)>>1;
	double s=0;
	if(l<=mid)
		s+=qry(t[x].ls,l,r);
	if(r>mid)
		s+=qry(t[x].rs,l,r);
	return s;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,q;
	cin>>n>>q;
	build(1,n);
	cout<<fixed<<setprecision(12);
	while(q--)
	{
		string op;
		cin>>op;
		if(op[0]=='s')
		{
			int l,r;
			cin>>l>>r;
			double s=qry(1,l,r);
			change(1,l,r,s/(r-l+1));
		}
		else
		{
			int p;
			cin>>p;
			cout<<qry(1,p,p)<<"\n";
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 6
1 2 3
get 1
get 3
shuffle 1 2
shuffle 2 3
get 1
get 3

output:

1.000000000000
3.000000000000
1.500000000000
2.250000000000

result:

ok 4 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

1 1
1000000
get 1

output:

1000000.000000000000

result:

ok found '1000000.000000000', expected '1000000.000000000', error '0.000000000'

Test #3:

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

input:

10 12
1 2 3 4 5 6 7 8 9 10
shuffle 1 9
get 5
shuffle 2 10
get 5
shuffle 1 9
get 5
shuffle 2 10
get 5
shuffle 1 9
get 5
shuffle 2 10
get 5

output:

5.000000000000
5.555555555556
5.493827160494
5.500685871056
5.499923792105
5.500008467544

result:

ok 6 numbers

Test #4:

score: 0
Accepted
time: 295ms
memory: 19600kb

input:

250000 250000
68757 751955 703680 711219 267765 466086 636464 19954 334163 71056 717004 301227 647670 658407 470976 962212 333132 359043 63961 97576 653283 56321 577801 762183 537904 962308 215335 233620 167947 398127 520621 865318 657201 399020 524920 437975 740097 331240 701964 724872 987328 58427...

output:

871685.000000000000
521328.000000000000
499414.277879421657
442339.000000000000
56707.000000000000
525320.000000000000
353040.000000000000
394070.000000000000
639336.000000000000
981278.000000000000
500700.622212197457
500700.622212197457
303526.000000000000
209826.000000000000
640302.000000000000
5...

result:

ok 125249 numbers

Test #5:

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

input:

250000 250000
217446 545330 797253 138733 836806 400690 356556 704610 593783 31517 367920 106479 863173 482377 906999 85427 925522 5057 124030 132 352277 730243 29749 244715 904918 366659 381406 11619 24883 961254 347218 242014 795551 51592 936892 13440 194205 697014 203612 838690 224905 775285 1626...

output:

98683.000000000000
867598.000000000000
734026.000000000000
732398.000000000000
631324.000000000000
642563.000000000000
965410.000000000000
367207.000000000000
501433.104622149083
385081.000000000000
375734.000000000000
135696.000000000000
499972.354090698995
499985.391615489847
124956.000000000000
1...

result:

ok 123407 numbers

Test #6:

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

input:

250000 250000
618495 779554 50796 893989 362953 86927 80281 237165 651176 629830 574523 624300 258760 908884 21160 433513 899018 822492 547243 875135 132483 657555 996738 583711 287164 897091 251360 9099 558512 532296 406956 551389 398544 265878 429953 478910 34306 525425 848044 945647 432286 171379...

output:

499502.799050199799
500203.731431419903
500203.731431419903
499487.307659206213
499552.267443656572
499552.267443656572
245944.000000000000
499819.623978129239
737044.000000000000
499979.107627671037
499529.508385404828
594626.000000000000
499436.718230842089
436199.000000000000
443577.000000000000
...

result:

ok 125038 numbers

Test #7:

score: 0
Accepted
time: 291ms
memory: 19692kb

input:

250000 250000
439989 436331 294774 2632 764017 260911 368365 953437 618577 147259 882566 739548 136794 297603 101927 873383 493812 916665 932762 365925 615210 201880 9486 964226 878445 98268 733204 937580 119570 584391 83874 974039 556303 741022 303060 27258 532098 756842 164198 306576 228778 659320...

output:

10590.000000000000
170267.000000000000
499083.869392454333
499083.869392454333
907053.000000000000
356471.000000000000
344170.000000000000
566185.000000000000
499090.774946107063
767941.000000000000
771256.000000000000
10346.000000000000
218805.000000000000
230044.000000000000
498340.507942106691
49...

result:

ok 125118 numbers

Test #8:

score: 0
Accepted
time: 304ms
memory: 19464kb

input:

250000 249999
270198 378495 92276 498035 325366 159800 225533 108786 33186 296420 254579 467116 55565 223468 455708 288403 67263 96276 34768 452909 455235 134163 410380 352253 43822 482519 63371 122185 180270 74031 328024 18650 276537 304055 317829 137623 498873 408360 196871 3298 211103 126533 3952...

output:

153208.000000000000
487522.000000000000
256563.605192950083
256486.848137449153
256734.878951871040
256486.848137449153
373365.000000000000
1145.000000000000
162145.000000000000
256329.788717792078
256446.121169691498
256446.121169691498
256329.788717792078
256486.848137449153
256446.121169691498
25...

result:

ok 124999 numbers

Test #9:

score: 0
Accepted
time: 72ms
memory: 3936kb

input:

1 250000
78531
shuffle 1 1
get 1
get 1
get 1
get 1
get 1
get 1
get 1
shuffle 1 1
shuffle 1 1
get 1
get 1
get 1
shuffle 1 1
get 1
shuffle 1 1
shuffle 1 1
get 1
get 1
get 1
get 1
get 1
get 1
shuffle 1 1
get 1
get 1
get 1
get 1
shuffle 1 1
shuffle 1 1
shuffle 1 1
shuffle 1 1
get 1
shuffle 1 1
get 1
get...

output:

78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000000
78531.000000000...

result:

ok 126508 numbers

Test #10:

score: 0
Accepted
time: 258ms
memory: 19468kb

input:

249853 250000
1 2 2 1 2 2 2 1 2 2 1 2 2 2 2 2 1 1 2 2 1 2 1 1 2 2 2 1 1 1 2 1 1 1 1 1 1 2 2 1 1 2 1 2 2 2 2 2 1 1 2 1 2 1 1 1 1 1 2 2 1 2 2 1 2 2 1 1 1 1 2 2 1 2 1 2 1 1 2 1 2 2 2 1 2 1 2 2 2 1 2 2 1 1 1 1 2 1 2 1 1 2 1 2 1 2 2 1 1 1 2 1 2 2 1 2 1 2 1 1 1 1 1 1 1 1 1 2 2 2 1 1 1 2 1 1 1 2 1 1 2 2 2 ...

output:

1.499716939358
1.000000000000
1.499716939358
1.499952683651
1.499952683651
1.499952683651
1.499952683651
1.499952683651
1.499716939358
1.499716939358
1.499909825816
1.499909825816
1.499909825816
1.499716939358
1.499917461052
1.499910973810
1.499958078628
1.499965089044
1.499716939358
1.499940531946
...

result:

ok 120568 numbers

Test #11:

score: 0
Accepted
time: 279ms
memory: 19420kb

input:

250000 250000
517111 432871 277460 193832 793398 224202 841896 512977 515023 764885 36466 509996 8316 592903 452096 540892 733246 970693 128548 212519 694295 939159 20338 589880 104462 457768 948740 488988 11503 622921 176054 13445 402441 728174 344617 435402 163118 6127 846276 141221 979318 18633 1...

output:

102370.000000000000
799765.000000000000
426346.000000000000
387683.000000000000
997636.000000000000
262032.000000000000
417403.000000000000
31431.000000000000
474864.000000000000
255777.000000000000
219622.000000000000
705390.000000000000
593007.000000000000
719819.000000000000
109622.000000000000
3...

result:

ok 249787 numbers

Test #12:

score: 0
Accepted
time: 265ms
memory: 19524kb

input:

250000 250000
130773 902188 469896 17261 451505 865039 704126 560411 811867 2281 368863 80305 515081 612130 916203 1586 752677 450485 622038 899442 200784 956979 320714 736861 292570 996735 929315 195438 959115 633169 940849 447096 731870 763507 662906 473249 527616 763591 916853 365474 528789 86457...

output:

575392.000000000000
327376.000000000000
804908.000000000000
91940.000000000000
578100.000000000000
412727.000000000000
920026.000000000000
37764.000000000000
847991.000000000000
403561.000000000000
490510.000000000000
289955.000000000000
346782.000000000000
927960.000000000000
219798.000000000000
42...

result:

ok 247952 numbers

Test #13:

score: 0
Accepted
time: 312ms
memory: 19564kb

input:

250000 250000
886012 632132 848689 226875 6859 899338 166771 834257 772997 611279 669490 617059 437671 787983 575662 449663 52308 441865 718796 456694 884883 378113 814420 360862 3981 85949 992305 323727 983824 611465 556789 955367 169486 311027 680658 299590 220574 590159 260257 890770 475770 67966...

output:

536946.000000000000
499956.658996362006
499718.835452020750
499709.411254738283
500015.796863947879
499994.571439265390
499975.045739316556
499979.475751734979
499983.073819099634
499980.907724662859
499957.804382036789
499979.427653864142
499980.207007638412
499980.207007638412
499976.014077993284
...

result:

ok 15433 numbers

Test #14:

score: 0
Accepted
time: 308ms
memory: 19696kb

input:

250000 250000
877147 521310 205733 7518 630750 903414 682978 115677 45474 336737 242931 228564 356579 644163 108109 417646 512174 416947 853879 991051 523812 657082 511373 778818 150203 165080 512445 168730 1916 723519 928909 504719 702086 267158 385299 106324 182602 96055 325435 67083 245261 446449...

output:

47821.000000000000
498562.610643345746
514077.000000000000
501859.234718685853
501859.234718685853
615420.000000000000
502116.631257339206
49553.000000000000
791976.000000000000
501074.731558039028
890819.000000000000
498562.610643345746
501483.718470550783
501585.193494460837
501749.257498468563
50...

result:

ok 83129 numbers

Test #15:

score: 0
Accepted
time: 257ms
memory: 19520kb

input:

250000 250000
949924 645189 430058 711120 520444 839523 9728 159735 903789 506317 482057 737554 191148 719165 757769 115644 271214 793038 367562 257330 73072 157441 180314 711064 92463 199801 516552 925746 629424 760191 717227 76780 756921 52862 383707 402067 558038 985928 130678 213210 564821 39617...

output:

454112.000000000000
352034.000000000000
284691.000000000000
759438.000000000000
913286.000000000000
246234.000000000000
190580.000000000000
569397.000000000000
689715.000000000000
274703.000000000000
956087.000000000000
456862.000000000000
212734.000000000000
569545.000000000000
928741.000000000000
...

result:

ok 83198 numbers

Test #16:

score: 0
Accepted
time: 217ms
memory: 19692kb

input:

250000 250000
1000000 1000000 2 2 2 1 1 2 2 1 1 1 2 1 1 1 1 2 2 2 1 1 2 2 1 2 2 2 2 1 1 2 1 2 1 1 2 1 1 1 1 1 2 2 2 1 2 2 2 2 1 2 1 2 1 1 1 2 2 1 1 2 1 2 1 2 2 1 1 2 1 2 2 1 2 2 2 2 2 2 1 2 1 1 1 1 2 2 2 2 2 1 1 1 2 1 2 2 2 1 1 1 1 2 1 2 1 1 1 1 1 1 2 1 2 1 1 2 1 2 2 1 2 1 1 2 2 1 1 1 1 2 2 2 2 2 1 ...

output:

1.000000000000
1.000000000000
1.000000000000
1.000000000000
2.000000000000
1.000000000000
2.000000000000
1.000000000000
1.000000000000
2.000000000000
2.000000000000
1.000000000000
1.000000000000
1.000000000000
2.000000000000
2.000000000000
2.000000000000
2.000000000000
2.000000000000
1.000000000000
...

result:

ok 124937 numbers

Test #17:

score: 0
Accepted
time: 237ms
memory: 19528kb

input:

250000 250000
92 839270 10 906896 66 663697 20 581144 28 963098 93 573927 42 799996 79 516357 87 982639 60 984404 63 620946 61 660393 44 843417 6 709232 42 803254 52 700099 77 991243 100 516140 27 865655 97 547137 66 780796 21 712488 43 625433 20 966954 42 538571 24 714993 16 793329 76 668625 33 652...

output:

16.000000000000
999747.000000000000
13.000000000000
988784.000000000000
56.000000000000
5.000000000000
863519.000000000000
977491.000000000000
90.000000000000
33.000000000000
645835.000000000000
974038.000000000000
544890.000000000000
984454.000000000000
11.000000000000
36.000000000000
85.0000000000...

result:

ok 124868 numbers

Test #18:

score: 0
Accepted
time: 257ms
memory: 19504kb

input:

250000 250000
1000000 1000000 1 1 1 2 1 2 2 1 2 2 2 2 2 2 1 1 1 2 1 1 1 1 2 2 1 1 1 2 2 2 1 2 1 1 1 1 1 2 2 1 1 2 2 2 1 1 1 1 1 2 1 1 2 2 1 2 2 1 1 1 1 2 2 2 1 2 1 2 1 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 1 1 2 1 2 2 2 1 2 2 2 1 1 2 2 1 1 2 1 2 2 2 1 1 1 2 2 2 2 1 1 2 2 2 1 1 1 1 1 1 1 ...

output:

1.000000000000
1.000000000000
2.000000000000
1.000000000000
2.000000000000
2.000000000000
1.000000000000
53.871618080158
1.000000000000
1.000000000000
2.000000000000
2.000000000000
1.000000000000
2.000000000000
2.000000000000
1.000000000000
15.625624602906
1.000000000000
2.000000000000
13.2144747411...

result:

ok 124957 numbers

Test #19:

score: 0
Accepted
time: 267ms
memory: 19464kb

input:

250000 250000
1000000 1000000 1 2 2 2 1 1 2 1 2 2 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 2 2 1 1 1 1 1 2 1 2 1 2 1 1 2 2 1 2 1 2 2 1 1 1 2 1 1 1 1 1 1 2 2 1 2 2 2 2 1 2 1 1 2 1 2 1 1 1 1 1 1 1 2 2 1 2 1 2 2 1 1 1 1 1 1 1 1 1 2 2 2 2 1 2 2 1 2 1 1 1 1 2 1 1 2 2 1 2 1 1 1 2 2 1 2 1 2 2 2 1 2 2 2 1 2 2 2 ...

output:

1.000000000000
1.000000000000
78.097851480219
1.000000000000
1.000000000000
1.000000000000
2.000000000000
1.000000000000
1.000000000000
47.438244078429
2.000000000000
2.000000000000
43.686155892634
1.000000000000
21.088372053318
2.000000000000
1.000000000000
2.000000000000
2.000000000000
2.000000000...

result:

ok 124975 numbers

Test #20:

score: 0
Accepted
time: 261ms
memory: 19524kb

input:

250000 250000
1000000 1000000 1 1 1 1 2 2 2 1 2 1 1 1 1 1 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 1 2 1 2 1 1 2 1 1 2 1 1 2 1 1 1 2 2 1 2 2 2 1 1 1 2 1 2 2 1 1 1 1 2 2 2 1 1 1 2 1 2 2 1 2 1 1 1 1 1 2 1 2 2 2 2 2 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 2 2 2 1 2 1 2 1 2 1 2 1 1 1 1 2 2 1 2 1 1 2 2 1 1 2 ...

output:

1.000000000000
2.000000000000
1.000000000000
1.000000000000
1.000000000000
2.000000000000
1.000000000000
2.000000000000
2.000000000000
2.000000000000
30.492570200675
47.048893241028
13.252329924903
6.259615419349
40.682067366092
10.197214107889
2.407787018953
35.204228792906
2.927253053808
47.048893...

result:

ok 124947 numbers

Test #21:

score: 0
Accepted
time: 320ms
memory: 19696kb

input:

250000 250000
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:

60354.000000000000
43440.000000000000
141959.000000000000
80588.000000000000
88843.000000000000
114482.000000000000
42708.000000000000
187574.000000000000
47690.000000000000
63131.000000000000
84808.000000000000
129097.000000000000
243878.000000000000
7239.561838142426
191266.000000000000
245756.000...

result:

ok 124960 numbers

Test #22:

score: 0
Accepted
time: 291ms
memory: 19396kb

input:

250000 250000
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:

185588.000000000000
25453.843698761160
29320.097279119669
29320.097279119669
227084.000000000000
98910.000000000000
52612.507004655585
237556.000000000000
148603.000000000000
248551.000000000000
111698.000000000000
33503.703081589214
139646.000000000000
170347.000000000000
52612.507004655585
91282.4...

result:

ok 125103 numbers

Test #23:

score: 0
Accepted
time: 292ms
memory: 19412kb

input:

250000 250000
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:

67121.000000000000
226093.000000000000
177344.000000000000
234681.000000000000
198534.000000000000
31956.500000000000
194416.000000000000
156341.000000000000
81396.000000000000
117389.000000000000
219467.000000000000
248077.000000000000
92277.000000000000
241424.000000000000
174637.000000000000
1158...

result:

ok 124924 numbers

Test #24:

score: 0
Accepted
time: 269ms
memory: 19472kb

input:

250000 250000
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:

69745.000000000000
220265.000000000000
206634.000000000000
49513.004090991730
49513.004090991730
106262.000000000000
198946.000000000000
149155.000000000000
49535.518406673516
127911.000000000000
166563.000000000000
49549.031902000468
121358.000000000000
49558.042942398104
182547.000000000000
185574...

result:

ok 124868 numbers

Test #25:

score: 0
Accepted
time: 292ms
memory: 19528kb

input:

250000 250000
401 85 238 1046 216 459 369 714 227 10 873 12 13 1318 186 637 251 80 453 239 975 267 366 89 281 260 25 532 647 359 315 151 317 287 2018 53 6 1093 226 40 276 1429 521 1155 126 26 901 748 589 527 395 1 204 54 520 56 440 609 1550 60 61 463 372 1230 405 378 67 1573 78 46 71 774 256 74 247 ...

output:

187533.000000000000
89729.000000000000
103120.000000000000
206937.000000000000
224025.000000000000
60276.000000000000
163400.000000000000
53350.000000000000
175129.000000000000
192575.000000000000
230698.000000000000
199291.000000000000
25458.628685255444
151260.000000000000
94282.000000000000
74342...

result:

ok 124841 numbers

Test #26:

score: 0
Accepted
time: 309ms
memory: 19404kb

input:

249999 249999
244 634 28 1079 309 809 470 802 42 448 11 12 867 447 175 906 41 415 19 128 424 965 23 24 335 26 149 315 51 30 105 87 241 16 325 797 32 328 434 805 439 122 1 452 308 458 27 651 431 973 265 52 282 222 197 540 198 66 15 646 61 65 613 1441 199 124 67 418 636 940 18 135 410 1037 1411 1056 2...

output:

51722.000000000000
206788.000000000000
168913.000000000000
82472.000000000000
196913.000000000000
206268.000000000000
24422.053770190418
35856.248848796000
151681.000000000000
20827.424954471218
24422.053770190418
117118.000000000000
145206.000000000000
233817.000000000000
51870.232883966506
17397.8...

result:

ok 124992 numbers

Test #27:

score: 0
Accepted
time: 273ms
memory: 19636kb

input:

249998 249998
1200 50 26 5 815 652 506 843 261 435 678 568 532 224 15 16 161 1234 361 20 21 83 266 24 432 696 63 646 603 30 433 146 482 216 1180 137 417 668 39 538 357 411 464 232 7 545 337 310 454 98 233 263 498 791 55 878 608 282 320 187 61 262 462 666 613 782 244 1019 37 418 457 23 1170 766 516 2...

output:

244449.000000000000
241619.000000000000
134281.000000000000
42750.929597000380
214933.000000000000
140112.000000000000
42793.060276676915
245183.000000000000
242967.000000000000
42835.178454895955
175049.000000000000
246943.000000000000
42887.957343357040
121327.000000000000
42887.957343357040
96642...

result:

ok 124902 numbers

Test #28:

score: 0
Accepted
time: 302ms
memory: 19464kb

input:

250000 250000
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:

109372.000000000000
173706.000000000000
97042.000000000000
103981.000000000000
166797.000000000000
122978.000000000000
113513.000000000000
111107.000000000000
73786.000000000000
18732.129367962323
81320.000000000000
48936.000000000000
19209.014749106511
87737.000000000000
19209.014749106511
19209.01...

result:

ok 125033 numbers

Test #29:

score: 0
Accepted
time: 243ms
memory: 19632kb

input:

250000 250000
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:

75622.000000000000
75622.000000000000
75624.000033059157
75624.000033059157
75624.000033059157
244734.000000000000
204681.000000000000
233881.000000000000
75624.500049588634
218374.000000000000
75627.000181822979
75627.000181822979
197072.000000000000
75627.000181822979
75627.000181822979
75627.0001...

result:

ok 124961 numbers

Test #30:

score: 0
Accepted
time: 245ms
memory: 19696kb

input:

250000 250000
556 597 26 658 729 6 58 8 9 880 1095 162 81 14 756 588 3 16 270 94 616 513 1666 728 1394 477 39 709 282 127 441 168 122 760 131 748 746 973 327 655 253 42 43 66 691 476 1307 982 11 335 347 60 53 218 242 328 872 59 92 420 292 76 239 1059 630 153 101 363 1089 500 372 455 105 487 364 484 ...

output:

128121.000000000000
173042.000000000000
181962.000000000000
208044.000000000000
187505.000000000000
49276.099910799247
200990.000000000000
219325.000000000000
49277.618453713905
160244.000000000000
205419.000000000000
101148.000000000000
136036.000000000000
210216.000000000000
221120.000000000000
23...

result:

ok 124947 numbers

Test #31:

score: 0
Accepted
time: 285ms
memory: 19496kb

input:

250000 250000
118 2 189 598 417 778 194 1051 237 359 935 673 852 579 15 16 47 18 1086 172 431 63 446 269 25 472 238 54 152 875 719 424 261 223 1519 36 738 150 39 40 784 146 510 526 587 46 883 1045 611 50 186 154 365 29 270 597 753 58 13 139 928 102 1163 259 752 164 369 794 61 70 688 188 410 52 235 7...

output:

236809.000000000000
247250.000000000000
64136.000000000000
200491.000000000000
228782.000000000000
104764.000000000000
38562.000000000000
177405.000000000000
237496.000000000000
155177.000000000000
54789.000000000000
246871.000000000000
244902.000000000000
99175.000000000000
30535.000000000000
22478...

result:

ok 83289 numbers

Test #32:

score: 0
Accepted
time: 277ms
memory: 19696kb

input:

250000 250000
1 2 20 3 1 1 3 2 1 6 1 2 5 2 5 1 1 1 2 2 1 14 2 2 1 2 5 5 3 1 1 10 1 5 1 18 1 1 1 14 12 2 2 1 9 4 2 5 6 14 11 1 3 21 2 11 1 23 1 1 2 9 23 11 1 2 1 2 2 1 1 2 2 1 19 11 9 4 7 1 2 11 5 1 1 2 1 3 11 5 2 1 1 34 1 2 13 1 2 2 5 2 3 5 5 5 1 1 7 1 12 5 1 2 3 21 2 1 1 5 1 9 2 1 1 1 2 2 2 1 5 6 1...

output:

467934.000000000000
18347.000000000000
41606.000000000000
150450.000000000000
9.000000000000
703819.900952557102
834807.000000000000
126666.000000000000
352394.000000000000
726283.616126256296
56412.000000000000
628975.000000000000
902782.000000000000
35778.000000000000
156516.000000000000
527741.00...

result:

ok 83216 numbers

Test #33:

score: 0
Accepted
time: 297ms
memory: 19408kb

input:

250000 250000
7 18 25 33 42 50 59 72 85 97 102 117 128 135 147 154 161 170 182 200 210 229 245 261 272 282 292 312 322 335 346 353 367 379 392 403 413 428 435 449 463 475 484 494 505 518 526 540 554 565 580 587 602 610 620 633 647 657 670 680 691 700 716 721 733 748 761 767 789 797 816 827 839 855 8...

output:

714747.000000000000
626700.000000000000
289705.000000000000
990597.000000000000
992211.000000000000
85335.000000000000
977227.000000000000
997106.000000000000
763075.000000000000
38351.000000000000
985544.000000000000
966201.000000000000
955946.000000000000
999952.000000000000
976092.000000000000
89...

result:

ok 83390 numbers

Test #34:

score: 0
Accepted
time: 298ms
memory: 19468kb

input:

249999 249999
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

390098.000000000000
3385.000000000000
10935.000000000000
14619.000000000000
55022.000000000000
85971.000000000000
729718.000000000000
23447.000000000000
2007.000000000000
52264.000000000000
3391.000000000000
1.000000000000
8.000000000000
946774.000000000000
6.000000000000
506877.000000000000
932137....

result:

ok 83131 numbers

Test #35:

score: 0
Accepted
time: 299ms
memory: 19524kb

input:

249999 249999
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

92199.000000000000
163782.000000000000
205770.000000000000
285498.000000000000
50722.000000000000
156.000000000000
488568.000000000000
226.000000000000
21387.000000000000
57376.000000000000
10013.000000000000
1375.000000000000
86425.000000000000
631505.976681846543
20695.000000000000
4004.0000000000...

result:

ok 83218 numbers

Test #36:

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

input:

250000 250000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

9363.000000000000
86447.000000000000
29496.084891612332
385933.000000000000
29648.360948400205
589489.000000000000
29476.813109529336
436300.000000000000
29476.813109529336
264180.000000000000
65471.000000000000
78131.000000000000
527668.000000000000
8488.000000000000
31.000000000000
137481.00000000...

result:

ok 75680 numbers

Test #37:

score: 0
Accepted
time: 294ms
memory: 19468kb

input:

250000 250000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

30469.000000000000
241964.542749409418
802746.284219756257
57801.765200277863
908.000000000000
350350.000000000000
540913.000000000000
4799.000000000000
95478.000000000000
6535.000000000000
3.000000000000
429795.000000000000
520117.000000000000
102093.000000000000
60246.030588119509
136480.000000000...

result:

ok 75680 numbers

Test #38:

score: 0
Accepted
time: 288ms
memory: 19528kb

input:

250000 250000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

355993.000000000000
146.000000000000
572907.000000000000
73544.000000000000
107969.000000000000
62672.000000000000
1372.000000000000
13442.000000000000
46351.960923627448
547611.000000000000
239194.584199507895
1863.000000000000
262324.044994065887
6458.000000000000
14901.000000000000
285846.9284768...

result:

ok 75680 numbers

Test #39:

score: 0
Accepted
time: 301ms
memory: 19460kb

input:

250000 250000
1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 1 1 1 1 ...

output:

631015.820243256749
97736.000000000000
2.000000000000
221349.000000000000
149088.000000000000
69857.794454121744
231442.882051282038
39.000000000000
1532.000000000000
14973.962387055228
219459.603217480268
172.000000000000
453419.000000000000
2541.000000000000
294752.000000000000
3.000000000000
2768...

result:

ok 75680 numbers

Test #40:

score: 0
Accepted
time: 316ms
memory: 19464kb

input:

250000 250000
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 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 1 1 1 1 2 1 2 1 1 1 2 1 1 1 1 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 ...

output:

39234.000000000000
667109.000000000000
218057.130076920323
508503.000000000000
56721.000000000000
67631.000000000000
338792.000000000000
29488.000000000000
36807.000000000000
288139.749329165963
82270.000000000000
324284.522656709771
708601.653338635806
131657.000000000000
439723.595148914261
529087...

result:

ok 75680 numbers

Test #41:

score: 0
Accepted
time: 267ms
memory: 19520kb

input:

250000 250000
5 1 2 40 1 5 2 6 1 1 1 1 14 1 2 1 14 1 3 1 17 1 2 14 3 1 2 1 1 9 14 3 1 1 2 6 1 1 2 1 5 2 1 1 9 6 14 2 1 1 2 14 3 1 1 2 1 1 1 1 30 1 1 2 6 1 1 4 2 17 3 7 4 1 1 5 2 68 14 49 5 1 1 1 2 2 1 36 32 1 1 1 1 9 10 1 3 16 5 6 1 1 14 2 6 4 1 18 9 1 2 2 1 1 21 2 1 2 14 1 2 2 2 1 44 14 9 11 6 4 1 ...

output:

875039.000000000000
823025.000000000000
791377.000000000000
161298.000000000000
144718.000000000000
933789.000000000000
196177.000000000000
317736.519152362016
633435.000000000000
440432.000000000000
319200.119455122214
172825.000000000000
710932.000000000000
319939.965412928257
104209.000000000000
...

result:

ok 124944 numbers

Test #42:

score: 0
Accepted
time: 261ms
memory: 19480kb

input:

250000 250000
3 43 11 1 5 1 11 3 15 1 16 3 3 3 1 5 1 8 6 7 8 9 1 1 1 3 1 4 8 2 3 2 6 1 2 17 2 1 8 3 2 1 17 1 3 1 3 4 1 7 27 5 1 5 8 2 12 1 1 2 3 1 1 1 1 1 3 35 5 2 3 8 8 2 8 11 1 7 17 2 4 2 19 50 1 7 7 17 15 2 1 2 2 2 14 1 8 2 21 2 1 3 1 1 1 1 1 3 81 1 1 8 1 10 1 17 2 1 18 106 1 14 4 17 35 6 3 1 2 1...

output:

116852.000000000000
288940.000000000000
968557.000000000000
13225.186560423901
13332.437719554318
725618.301647833316
363415.043112618674
363927.388863263186
726333.551981389872
13440.770698667771
726333.551981389872
538172.000000000000
126579.280525074981
217296.000000000000
364441.238628200721
364...

result:

ok 125081 numbers

Test #43:

score: 0
Accepted
time: 267ms
memory: 19524kb

input:

250000 250000
1 15 1 1 3 2 2 1 2 3 1 5 1 20 18 8 3 1 1 2 1 2 1 2 2 1 1 9 1 2 1 6 2 2 1 1 5 2 1 1 1 3 4 5 1 10 3 9 1 1 8 1 1 3 3 1 27 5 19 20 1 10 8 5 2 51 8 2 1 1 1 1 1 7 2 8 1 2 1 20 1 1 5 2 2 1 1 2 2 1 8 26 1 2 18 1 2 2 1 1 2 1 1 1 3 7 2 8 1 9 4 2 26 17 2 2 7 1 10 1 2 1 4 2 1 4 1 2 1 1 2 1 4 4 10 ...

output:

11233.838704073656
87926.354077998782
87926.354077998782
659268.000000000000
87926.354077998782
244953.771627725189
11332.573230706183
244953.771627725189
11332.573230706183
244953.771627725189
88185.649392650084
88185.649392650084
799498.482984570321
11432.624059782618
799498.482984570321
11432.624...

result:

ok 124972 numbers

Test #44:

score: 0
Accepted
time: 254ms
memory: 19468kb

input:

250000 250000
30 6 5 1 1 2 2 2 1 5 1 1 2 2 6 16 2 2 6 8 6 5 2 2 6 1 2 2 2 2 5 7 5 2 2 6 4 2 2 5 5 1 3 2 6 5 1 5 6 2 2 6 5 2 2 1 2 3 2 2 6 2 2 8 2 2 5 2 2 27 2 2 2 2 5 6 2 11 2 5 5 4 2 28 10 2 2 5 2 5 2 5 2 2 5 5 16 2 15 6 5 6 5 5 1 17 2 6 2 2 6 2 5 2 1 5 2 5 6 11 5 5 5 5 6 2 8 21 5 19 1 2 5 8 2 2 6 ...

output:

541021.625578719191
541203.449419202399
66872.046742226405
541385.871122693992
541385.871122693992
541385.871122693992
541568.250961821177
67144.403575426171
541933.218263516552
67144.403575426171
67212.889289168248
67212.889289168248
541933.218263516552
541933.218263516552
221686.000000000000
54193...

result:

ok 124852 numbers

Test #45:

score: 0
Accepted
time: 250ms
memory: 19528kb

input:

250000 250000
1 2 1 2 2 2 2 2 2 2 2 1 2 2 2 2 7 1 2 1 1 2 1 2 1 2 2 2 2 2 5 2 2 2 2 2 2 15 1 2 2 2 2 1 2 1 2 1 2 3 2 9 1 2 10 2 1 2 9 1 2 2 2 1 9 2 1 2 2 2 2 2 2 2 3 3 2 2 1 8 1 1 2 1 3 1 2 2 1 9 2 2 2 2 1 2 1 1 1 3 2 1 2 2 14 2 1 2 2 12 2 1 7 8 2 1 2 2 15 3 2 2 2 2 20 2 2 30 2 1 2 2 2 2 2 1 2 1 2 1...

output:

705964.000000000000
191063.000000000000
171487.000000000000
284809.000000000000
925489.000000000000
19900.018531869573
391349.060625921702
62033.000000000000
219511.000000000000
208852.000000000000
19903.884140172740
19903.884140172740
147022.000000000000
19905.215866073439
19905.215866073439
107873...

result:

ok 124949 numbers

Test #46:

score: 0
Accepted
time: 242ms
memory: 19524kb

input:

250000 250000
1 5 1 1 4 20 1 10 1 4 8 3 3 1 4 4 5 1 9 2 4 4 4 16 1 7 5 1 2 3 1 8 35 3 1 3 4 1 2 3 46 1 32 1 1 1 1 49 5 1 1 1 8 25 1 1 27 1 5 18 13 2 12 1 5 15 3 13 1 16 1 10 1 1 4 1 1 4 1 1 1 4 15 3 8 18 4 3 1 10 1 1 8 1 1 3 3 51 16 2 4 2 8 13 2 13 8 9 9 19 1 3 14 1 14 1 1 4 9 1 7 1 1 10 5 1 1 41 5 ...

output:

892168.000000000000
174566.998708262254
563165.382692574873
174588.137394118065
8966.599894770281
436734.000000000000
352479.000000000000
281939.000000000000
401211.000000000000
8966.599894770281
46816.000000000000
563190.349496697774
8968.310023954315
563214.892321279505
356599.000000000000
70472.0...

result:

ok 124950 numbers

Test #47:

score: 0
Accepted
time: 236ms
memory: 19596kb

input:

250000 250000
7 5 1 5 1 1 27 1 1 1 2 1 7 2 1 1 1 1 1 5 6 4 2 2 5 1 17 2 1 5 22 1 1 1 17 8 2 2 5 4 1 17 9 48 5 1 2 5 1 1 5 2 15 17 2 5 2 1 2 1 1 1 2 2 28 13 1 2 4 11 2 17 1 3 16 10 7 1 1 8 7 4 16 2 1 17 1 42 2 1 1 2 1 2 17 1 1 34 4 26 10 1 6 6 1 1 1 1 2 1 5 4 7 5 1 5 2 2 1 5 5 2 1 1 1 1 2 2 7 1 2 15 ...

output:

109831.000000000000
13073.000000000000
300321.000000000000
57352.000000000000
146612.000000000000
14004.222178675707
944067.000000000000
192797.064627383341
14004.776954749492
87684.000000000000
14005.361799707365
594063.293665252393
192800.789873185277
192800.789873185277
594063.293665252393
14005....

result:

ok 124925 numbers

Test #48:

score: 0
Accepted
time: 332ms
memory: 19696kb

input:

250000 250000
969436 180976 629243 113249 131921 602306 162946 18245 739856 948165 929930 919906 13569 422928 770177 897580 524223 656720 116814 753639 172823 558595 889225 235245 317838 428861 53822 5484 665432 911335 76015 465637 511777 287163 515471 669998 279496 820234 814791 648177 724575 73590...

output:

680416.000000000000
500829.586780905200
500848.794618470944
500843.112199632276
500841.296257298440
500549.560909652559
500616.224521299591
500616.459794960916
500615.304836997995
500615.450896747992
500615.304836997995
500615.485560705420
500615.485114070179
500615.421752600058
500613.212838686304
...

result:

ok 15433 numbers

Test #49:

score: 0
Accepted
time: 302ms
memory: 19468kb

input:

250000 250000
412416 61406 104380 315264 917025 352249 147125 876136 562831 458882 885740 896001 110338 638235 569750 587383 434570 731932 884857 67307 916231 874575 909171 812402 229678 556722 266161 950164 202891 176504 730617 583886 995001 139464 324641 492881 195500 249469 730773 177600 883815 5...

output:

34923.000000000000
500243.100149190403
500243.100149190403
500301.397569685068
59388.000000000000
499965.944399477972
499826.669721689716
499826.669721689716
500221.505589161068
499826.669721689716
499826.669721689716
500089.739876084903
500107.752424748149
500037.060616172152
499826.669721689716
50...

result:

ok 81065 numbers

Test #50:

score: 0
Accepted
time: 312ms
memory: 19464kb

input:

250000 250000
767258 557404 237891 887069 895016 559839 786099 295143 221286 789596 199175 264226 236249 591206 173580 579067 624309 23654 995969 487093 295207 336789 839964 352677 976652 370758 144326 24436 295799 957018 703770 968353 54703 254537 156906 771516 893934 884512 306938 271340 245603 94...

output:

965686.000000000000
499831.862830665312
883165.000000000000
236139.000000000000
499831.862830665312
499831.862830665254
782429.000000000000
499429.909777918423
499429.909777918423
499435.222809483123
499683.790464699152
499672.003178177751
499831.862830665254
499827.227725578763
499827.227725578763
...

result:

ok 76787 numbers

Test #51:

score: 0
Accepted
time: 307ms
memory: 19700kb

input:

250000 250000
685504 371599 964304 502628 417271 928030 426832 151967 977757 424013 770000 806514 693893 604004 628179 630949 386692 781580 772321 175780 960882 315539 71812 726398 239020 877100 381836 54569 716308 432300 216843 492859 204495 802126 368666 237554 313926 174832 519442 781550 45798 15...

output:

500106.286750020925
499500.771658751648
499458.367584816297
760171.000000000000
499484.137678240368
499484.137678240368
499458.367584816297
205736.000000000000
499398.283665626019
499398.283665626019
499381.721570087015
499398.283665626077
499248.611405201955
499362.595995801676
499362.595995801676
...

result:

ok 67856 numbers