QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#403403#8127. Slučajna Cestalfxxx#40 1951ms152220kbC++142.0kb2024-05-02 10:47:572024-05-02 10:47:58

Judging History

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

  • [2024-05-02 10:47:58]
  • 评测
  • 测评结果:40
  • 用时:1951ms
  • 内存:152220kb
  • [2024-05-02 10:47:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 1e6 + 5, mod = 1e9 + 7;
vector<int>e[N];
int n, a[N], dp[N], tp[N], ans[N];
inline int qpow(int b, int k)
{
	int res = 1;
	while (k) {
		if (k & 1) res = (ll) res * b % mod;
		b = (ll) b * b % mod;
		k >>= 1;
	}
	return res;
}
void dfs1(int u, int f)
{
	int c = e[u].size() - (u != f);
	dp[u] = a[u];
	for (int v : e[u]) {
		if (v != f) {
			dfs1(v, u);
			dp[u] = (dp[u] + (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) % mod * dp[v]) % mod;
		}
	}
}
void hg(int u, int v)
{
	int c = e[u].size();
	dp[u] = (dp[u] - a[u]) % mod;
	dp[u] = (dp[u] - (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) * dp[v]) % mod;
	dp[u] = (ll) dp[u] * 2 % mod * (tp[c - 1] - 1) % mod * c % mod * qpow((ll) (tp[c] - 1) * (c - 1) % mod, mod - 2) % mod;
	dp[u] = (dp[u] + a[u]) % mod;
	c = e[v].size();
	dp[v] = (dp[v] - a[v]) % mod;
	dp[v] = (ll) dp[v] * (tp[c] - 1) % mod * (c - 1) % mod * qpow(2ll * (tp[c - 1] - 1) % mod * c % mod, mod - 2) % mod;
	dp[v] = (dp[v] + (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) * dp[u]) % mod;
	dp[v] = (dp[v] + a[v]) % mod;
}
void dfs2(int u, int f)
{
	ans[u] = (dp[u] + mod) % mod;
	for (int v : e[u]) {
		if (v != f) {
			hg(u, v);
			dfs2(v, u);
			hg(v, u);
		}
	}
}
bool en;
int main()
{
	cerr << (&be - &en) / 1024.0 / 1024 << " MB\n--------------------------------" << endl;
#ifdef IAKIOI
	freopen("in.in", "r", stdin);
//	freopen("out.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 2; i <= n; ++i) {
		int f;
		cin >> f;
		e[f].emplace_back(i);
		e[i].emplace_back(f);
	}
	for (int i = 1; i <= n; ++i) cin >> a[i];
	tp[0] = 1;
	for (int i = 1; i <= n; ++i) {
		tp[i] = tp[i - 1] * 2ll % mod;
	}
	dfs1(1, 1);
	dfs2(1, 1);
	for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 6ms
memory: 27724kb

input:

2
1
307903 536004

output:

575905
500689959

result:

ok all correct

Test #2:

score: 10
Accepted
time: 8ms
memory: 29212kb

input:

3
1 2
992649 690492 637324

output:

1497226
876301738
251230734

result:

ok all correct

Test #3:

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

input:

4
1 2 3
826918 524416 30987 233038

output:

501126006
889825
375470082
250483002

result:

ok all correct

Test #4:

score: 10
Accepted
time: 4ms
memory: 29304kb

input:

5
1 2 3 4
859332 957641 552087 294350 114098

output:

126520100
939052817
751204107
938304296
125572709

result:

ok all correct

Test #5:

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

input:

6
1 2 2 4 5
91742 92552 191745 529457 181043 884683

output:

47206686
156670572
984787945
922712805
617936136
829257432

result:

ok all correct

Test #6:

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

input:

7
1 1 3 4 4 6
69032 207537 280790 889967 218886 618588 754535

output:

293473187
945792944
24287651
511768034
204044442
255223945
87278766

result:

ok all correct

Test #7:

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

input:

8
1 2 2 4 2 6 7
546075 347525 670520 983062 581593 336046 97830 706738

output:

334418635
329187863
605358267
243713478
246081337
164970462
770221487
347328072

result:

ok all correct

Test #8:

score: 10
Accepted
time: 0ms
memory: 27636kb

input:

9
1 2 3 3 5 1 7 8
817515 848951 198209 119142 819728 367379 501231 458709 804045

output:

778945070
884374888
701481221
254592128
137000383
674805839
311894676
750233527
417348933

result:

ok all correct

Test #9:

score: 10
Accepted
time: 0ms
memory: 27556kb

input:

10
1 1 1 4 5 4 1 8 8
874755 324368 592836 600006 266724 217696 423188 402322 557734 423393

output:

616715460
217237546
634133532
688080628
590912992
60727477
121167098
530612063
430789154
868180005

result:

ok all correct

Test #10:

score: 10
Accepted
time: 6ms
memory: 28424kb

input:

10
1 2 3 1 5 6 7 7 9
195744 206104 723327 114978 178292 190130 540646 250919 152931 940237

output:

158806482
79765837
290477198
526950480
317003915
633487763
313413032
531963588
860175194
157463149

result:

ok all correct

Test #11:

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

input:

10
1 2 2 4 5 4 7 1 9
160335 133086 186701 906673 561321 529327 813569 759454 327734 62760

output:

612909843
659626152
629535210
48467043
569673492
130085768
77772881
52282583
56718813
704471661

result:

ok all correct

Test #12:

score: 10
Accepted
time: 0ms
memory: 28964kb

input:

10
1 2 2 1 5 6 7 8 9
286342 884910 904819 108098 292165 78969 566381 587683 156711 111976

output:

821283130
567751781
374520609
61373271
149275061
51484565
229512794
771472918
448321820
132272409

result:

ok all correct

Test #13:

score: 10
Accepted
time: 0ms
memory: 29272kb

input:

10
1 1 3 3 5 6 6 6 9
820907 494966 187493 466984 150135 896410 388758 105418 191024 930665

output:

363066644
242278836
612403907
108326578
274335852
819650079
613004775
29429418
811535270
291689673

result:

ok all correct

Test #14:

score: 10
Accepted
time: 0ms
memory: 28772kb

input:

10
1 2 3 4 5 5 7 7 9
780617 360476 946142 170041 984436 863484 705401 759288 364152 323780

output:

792343871
562727727
562167115
91166936
840366602
290796618
770432943
924365902
661973330
774831032

result:

ok all correct

Test #15:

score: 10
Accepted
time: 0ms
memory: 28676kb

input:

10
1 2 2 1 5 5 1 1 9
996177 507917 928080 610241 428655 745973 313129 879790 3630 222636

output:

585661496
324752716
780879684
93121435
366439393
584327336
833975652
801152444
944125266
629583216

result:

ok all correct

Test #16:

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

input:

10
1 2 3 4 5 6 7 8 9
485357 872875 543104 252486 738854 873509 801028 59862 417026 867486

output:

739460169
733862443
778669222
462141515
876563208
978255004
317930623
65403099
345776883
397765700

result:

ok all correct

Test #17:

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

input:

10
1 1 3 1 5 6 6 8 5
405829 249733 974377 17147 381677 349987 698528 659718 383030 547497

output:

828512375
738117175
280840778
603744319
264086975
110768674
214583133
895570339
763890880
911231948

result:

ok all correct

Test #18:

score: 10
Accepted
time: 0ms
memory: 28604kb

input:

10
1 2 3 1 5 6 7 8 7
114148 888405 653482 324506 212949 908169 155568 180096 181076 166389

output:

809474092
686924034
656473190
604449927
836836772
782500753
768863726
321788284
881297985
199739646

result:

ok all correct

Test #19:

score: 10
Accepted
time: 0ms
memory: 28200kb

input:

10
1 1 3 4 5 6 7 6 9
878639 541255 25599 274902 119473 639010 97108 753448 96106 773930

output:

983622610
739341242
903019368
274169390
281959300
123432644
720471011
147529573
361101388
741298692

result:

ok all correct

Test #20:

score: 10
Accepted
time: 8ms
memory: 28624kb

input:

10
1 2 2 2 2 2 2 2 2
766887 885978 73938 216251 903006 615990 205756 890530 603065 506057

output:

671137547
284402329
811845161
839566505
932739803
157080025
982378930
332142162
366784703
464349985

result:

ok all correct

Test #21:

score: 10
Accepted
time: 7ms
memory: 27288kb

input:

10
1 2 3 4 5 6 7 8 9
733342 202778 673543 829195 415681 35504 602267 386331 559518 466392

output:

735524386
852512262
329450881
470194237
94855921
266434302
571422189
161172655
331123819
887672425

result:

ok all correct

Test #22:

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

input:

10
1 2 2 1 4 4 6 3 8
904213 323773 607336 184293 233574 392314 370246 454542 257726 448337

output:

590656244
75229314
856033476
756000651
60461972
354421829
289846343
833907290
404114388
639532023

result:

ok all correct

Subtask #2:

score: 0
Wrong Answer

Test #23:

score: 30
Accepted
time: 0ms
memory: 28340kb

input:

100
1 2 1 4 5 6 7 7 9 9 5 12 5 4 1 16 17 18 18 20 20 22 23 24 25 23 27 28 27 30 31 32 27 34 35 36 37 38 39 39 41 38 43 43 45 46 43 48 49 49 49 48 48 54 55 56 57 57 55 60 60 62 55 64 65 64 67 67 69 69 69 72 37 74 75 76 76 78 76 80 81 82 80 84 85 74 87 87 89 89 91 89 87 94 94 96 97 98 98
754341 720186...

output:

744419112
868534785
579276734
966426530
89470157
365627670
936462279
93017671
603359319
522390035
22343082
205462129
636979071
211558039
86006737
525095665
167727115
994038924
460586504
309146514
877389799
199845255
163729135
868507823
372639715
82379059
856574083
348017654
982070262
781505719
17297...

result:

ok all correct

Test #24:

score: 0
Wrong Answer
time: 4ms
memory: 28204kb

input:

200
1 1 3 4 5 6 7 8 8 5 11 12 13 13 15 16 16 18 19 20 21 22 23 16 25 25 27 28 29 30 31 28 33 28 35 35 37 35 13 40 41 42 40 44 45 46 47 45 49 50 50 52 53 52 52 56 56 58 58 60 56 62 62 62 65 65 67 68 65 70 71 65 73 73 75 75 77 77 79 80 79 82 83 84 83 86 87 87 89 90 91 92 92 94 92 96 97 98 96 92 101 10...

output:

725084368
983709498
824961909
336358280
709426657
297523596
426557566
767786580
119003107
931503705
534694332
425258617
150579774
654744506
642042232
884679319
138214497
181144455
893410053
52582794
987525977
416233639
552678811
618456103
941998026
784721349
218719610
952238453
248625961
515894278
7...

result:

wrong output format Extra information in the output file

Subtask #3:

score: 30
Accepted

Test #54:

score: 30
Accepted
time: 96ms
memory: 31272kb

input:

60000
1 2 2 1 3 4 5 6 9 6 11 11 13 8 4 10 7 10 3 16 12 9 19 15 24 24 27 25 8 16 13 7 20 15 22 28 33 31 20 27 41 17 25 35 39 5 22 34 19 14 49 34 51 31 39 56 55 48 48 14 47 50 58 12 61 41 66 21 62 64 57 32 54 30 30 50 45 40 56 38 38 43 76 44 84 49 59 84 66 45 57 60 47 42 33 54 74 37 59 26 18 101 80 67...

output:

117639703
505499720
217392232
736598231
5788082
222979475
58628278
88739356
483103427
892979427
656931297
35461225
221784125
595137445
234234213
853473537
107407778
44940167
361717910
789976791
248194725
446646737
186263945
267774449
772729813
812060700
185754119
449015622
598022002
922192272
822202...

result:

ok all correct

Test #55:

score: 30
Accepted
time: 203ms
memory: 33136kb

input:

120000
1 1 2 3 5 4 5 6 8 10 11 2 9 14 14 9 16 12 6 16 7 17 11 24 7 18 21 3 13 29 23 12 8 20 20 27 22 31 13 19 39 36 18 37 38 24 47 17 4 15 35 39 23 48 50 21 30 34 10 60 57 51 34 63 33 58 27 30 69 46 66 46 61 69 68 31 54 36 57 25 47 80 48 45 85 19 62 88 50 54 22 66 67 89 76 74 80 87 74 75 59 41 32 10...

output:

727304663
355472490
462617883
941694097
689986532
682263666
596099564
338032623
562772851
35982083
590846989
881365594
391629792
317015282
589762863
776424897
909838528
843612804
380282938
313086297
407902883
212259529
801943217
182623029
689219952
353093239
236302099
591906911
962503319
160318152
2...

result:

ok all correct

Test #56:

score: 30
Accepted
time: 325ms
memory: 37592kb

input:

180000
1 1 3 4 2 4 3 7 2 7 5 6 11 5 11 13 8 13 19 8 6 19 9 23 23 21 22 28 29 28 17 22 30 33 20 30 10 27 21 25 9 12 37 41 18 43 26 46 26 45 14 34 10 48 54 12 47 51 29 51 45 59 44 34 48 60 38 64 32 62 55 39 58 49 14 76 68 54 49 32 52 37 56 25 38 84 43 59 83 42 36 33 83 84 90 78 77 79 80 62 68 53 53 31...

output:

125624698
360269195
114163212
992829457
128973868
205567918
398511928
424245128
617616178
338012939
388814477
136437309
974141592
873753113
615303295
276644353
979489222
581900833
113888039
595032785
723652701
756348240
194868716
12907458
314952980
236658151
109587921
487328299
606906709
954726517
3...

result:

ok all correct

Test #57:

score: 30
Accepted
time: 435ms
memory: 39748kb

input:

240000
1 1 3 2 2 3 6 6 9 10 9 4 13 5 5 14 12 10 8 14 4 19 18 18 15 11 23 26 28 28 23 13 29 16 25 22 27 17 30 33 15 33 36 17 24 37 19 21 20 42 48 25 46 43 35 56 20 36 29 54 51 22 38 44 34 16 39 57 59 68 12 30 8 41 71 58 66 39 64 57 71 37 38 68 27 82 62 65 11 43 81 88 40 94 77 26 47 53 70 49 31 31 45 ...

output:

986214575
391879844
313769139
988788582
582063594
716604697
540446330
377443771
401533213
34492372
384982640
454445589
4911223
784449196
389188243
67548065
615696023
151585232
870808843
518761490
976218926
363166900
710605865
623467875
106211884
156736621
953691903
865467745
566135268
481648566
8743...

result:

ok all correct

Test #58:

score: 30
Accepted
time: 526ms
memory: 41684kb

input:

300000
1 2 2 1 4 6 6 7 7 3 5 11 3 12 5 9 13 12 18 17 9 18 8 13 11 4 8 23 26 28 14 21 17 28 21 23 20 26 14 33 35 29 40 36 25 16 36 24 10 44 40 27 20 51 15 41 57 55 32 46 56 60 51 24 33 54 16 45 27 42 46 34 60 31 75 31 15 72 10 57 25 78 59 39 75 34 77 55 74 59 74 53 42 32 91 81 68 81 38 49 61 101 90 5...

output:

750785761
597404924
673403925
751419134
10718579
518101741
555640497
907224986
51818674
590609771
635692320
790839775
212618588
469669457
492495732
174195963
271828353
946990353
669109837
230112420
935060851
833777315
347012220
194524388
420629072
729937293
452119488
441086334
668908114
135599074
90...

result:

ok all correct

Test #59:

score: 30
Accepted
time: 640ms
memory: 44996kb

input:

360000
1 2 3 3 2 5 7 4 8 9 11 7 11 4 5 1 8 17 12 20 21 14 14 12 19 23 27 10 28 21 30 16 23 10 35 19 25 25 39 32 26 40 24 34 44 39 9 22 36 40 31 41 37 42 55 56 32 55 42 54 45 41 16 52 52 37 33 56 65 44 54 17 48 30 18 36 70 43 61 38 26 20 6 72 22 76 35 83 89 49 80 81 65 70 79 31 89 13 67 61 81 80 103 ...

output:

386620302
980588341
347083394
562055862
711003035
91247448
375101956
618309877
238529758
636332258
821602603
419200136
89387071
856004473
597904191
719995083
636809473
656249909
23537711
645094972
449693725
609160582
628867140
181682789
493333037
393960661
295482619
474705141
979224777
245171838
226...

result:

ok all correct

Test #60:

score: 30
Accepted
time: 770ms
memory: 47696kb

input:

420000
1 1 2 2 5 4 4 5 9 6 3 8 11 9 8 7 13 6 12 19 7 19 22 20 14 11 16 20 3 24 29 14 21 23 12 16 13 30 23 21 37 24 35 38 18 40 32 35 26 10 17 34 25 47 53 53 31 26 50 31 48 45 28 40 49 15 38 65 44 63 63 72 37 60 18 62 45 48 22 57 66 39 33 46 73 56 74 85 61 80 36 51 78 75 46 39 10 32 75 55 87 77 42 44...

output:

891229885
715977939
775201734
92135714
117564002
662375025
78928908
783087500
425484239
891160431
337979819
524470979
178370469
39507541
790150020
265761028
408037199
815328686
305467051
634848592
829682279
934008008
704167771
354224802
556946345
677986837
994973169
466546761
101491208
107153811
522...

result:

ok all correct

Test #61:

score: 30
Accepted
time: 880ms
memory: 50348kb

input:

480000
1 2 2 3 5 4 3 6 9 8 10 11 10 7 14 14 8 13 6 15 9 17 11 13 5 12 1 19 7 21 22 22 4 33 20 35 31 18 38 40 26 32 30 44 12 34 16 16 37 24 32 21 51 50 43 29 41 42 20 18 35 30 48 41 15 50 19 24 33 64 59 53 47 51 42 72 39 49 44 48 27 66 77 74 59 85 53 81 85 67 26 86 68 65 74 40 77 66 47 87 45 23 76 86...

output:

838857188
211732915
728920916
6097501
938782381
536183407
998705590
865721770
42475800
444960229
697676495
519727799
90131383
956160093
686096369
142976790
401525146
31252886
558447952
626521606
847493338
635781162
221312136
954915783
453882044
705789487
691995058
446131558
862250891
775810264
60812...

result:

ok all correct

Test #62:

score: 30
Accepted
time: 1024ms
memory: 54416kb

input:

540000
1 2 3 3 4 6 6 8 4 10 9 9 2 11 11 7 8 15 12 10 19 16 16 23 15 14 5 17 23 26 7 12 20 30 30 22 25 28 35 40 17 20 18 42 13 40 19 21 24 28 41 50 24 5 14 55 33 58 54 55 18 22 29 50 64 52 35 37 29 65 58 43 59 51 36 53 31 49 33 44 49 63 80 54 25 32 76 48 87 66 83 92 89 91 36 87 59 84 80 34 57 60 82 7...

output:

218337709
753563758
104923237
853597343
610199775
527932517
423050899
872943619
844067878
157157109
265064222
9640148
180803610
560389679
29311807
689638170
210729350
929830888
812526249
433617466
584961517
327285862
528366577
367213417
884056647
674119278
642036710
158605346
620455729
799670799
561...

result:

ok all correct

Test #63:

score: 30
Accepted
time: 1135ms
memory: 56092kb

input:

600000
1 2 3 4 3 5 5 4 2 8 1 7 10 8 11 13 11 18 10 7 13 18 15 6 17 20 26 19 29 12 23 31 14 30 35 12 27 24 29 15 28 16 16 37 41 36 25 19 46 33 41 32 45 27 54 46 17 48 34 59 36 34 57 48 58 53 65 32 44 62 6 54 59 49 50 63 40 58 43 51 55 66 49 84 76 51 65 87 9 22 86 14 31 37 89 95 66 79 40 79 44 42 47 7...

output:

196442068
94265043
21185905
996554435
331677968
841401316
315757248
583719505
843795594
274428568
226525614
611186096
479764490
614142723
753645904
102164865
35884426
988725491
795832988
89602098
391893811
619300934
521896498
794855348
135080045
384168994
512148256
756525131
768995985
678776163
4456...

result:

ok all correct

Test #64:

score: 30
Accepted
time: 1245ms
memory: 59268kb

input:

660000
1 2 3 2 1 6 3 7 8 9 4 8 9 13 13 5 5 7 17 10 20 18 15 23 17 11 19 18 28 30 29 6 21 15 19 27 34 12 16 16 31 35 23 44 36 44 22 14 31 42 48 24 53 37 12 14 55 30 48 35 59 22 36 42 59 45 11 39 21 66 34 56 55 66 27 46 20 32 71 73 81 25 26 37 80 10 87 68 47 67 41 60 84 67 77 57 47 83 28 29 46 68 97 3...

output:

82497201
204545685
213359758
399221318
648402308
635979772
673147729
706839903
173507611
477877493
459286700
489835447
667589662
279609800
580658090
755183011
796467253
158535731
114750187
797576932
581185214
143687729
851002555
296518048
549851243
497717843
796647313
939179788
720862026
496958971
3...

result:

ok all correct

Test #65:

score: 30
Accepted
time: 1411ms
memory: 62152kb

input:

720000
1 2 1 4 2 5 6 5 9 9 11 12 12 7 10 6 7 14 17 13 20 3 22 11 20 17 3 4 15 8 8 26 25 27 14 24 13 31 10 40 21 34 37 16 35 26 38 37 21 15 31 25 23 27 45 19 56 52 24 23 43 36 22 49 35 41 32 52 61 56 47 50 42 72 69 69 63 48 33 79 42 39 50 53 44 68 63 87 88 88 49 38 58 43 18 62 55 75 39 84 55 71 84 96...

output:

87265428
865359809
148327093
136140816
484258955
60120768
556012702
104049494
364602462
792792536
911720400
189345432
471503359
94775099
89140870
109517796
137483052
450767960
780387000
657040118
696995820
575082934
96175124
621335972
629753557
531040277
487337146
559273507
843172395
908341509
91271...

result:

ok all correct

Test #66:

score: 30
Accepted
time: 1507ms
memory: 64436kb

input:

780000
1 2 1 4 4 3 2 8 7 10 9 12 7 6 10 5 3 6 8 12 14 5 18 21 16 17 15 17 20 26 29 31 9 20 15 31 34 23 34 26 13 35 27 11 30 30 27 18 46 42 32 22 23 24 37 35 38 24 22 58 42 44 19 47 49 13 37 46 11 55 64 48 51 60 40 54 75 78 58 63 64 41 66 76 77 65 63 54 49 69 60 77 62 72 59 83 68 98 76 50 57 16 87 41...

output:

234259462
427967239
24858221
685220800
820878610
909754379
561396953
240758520
900192838
429911668
995174805
94473548
569600040
324108297
533519341
521264412
774513909
622957365
223075028
883126656
728215019
603621688
802976417
747241693
863479524
490630917
338986110
574403379
875394705
26650146
335...

result:

ok all correct

Test #67:

score: 30
Accepted
time: 1612ms
memory: 66792kb

input:

840000
1 1 3 3 2 4 5 6 6 5 8 2 12 10 4 7 16 7 14 16 17 9 23 8 15 24 15 12 11 30 27 29 25 23 19 9 21 34 14 10 27 41 32 31 45 19 17 20 24 20 26 48 21 51 26 44 57 36 41 46 30 31 50 33 35 18 18 55 53 42 69 33 60 46 58 61 57 51 68 34 13 22 58 52 39 75 32 84 53 61 64 67 85 54 22 63 89 98 54 40 25 40 60 72...

output:

987197784
342456680
319823997
431926075
866411343
443551775
373086547
220232702
237671602
863991970
197952355
177132547
637579006
475284219
30633113
907318739
417012204
210861099
396733928
501544963
539961237
534945009
695353381
899608709
943147778
736515614
291604809
892740753
631496892
358900890
4...

result:

ok all correct

Test #68:

score: 30
Accepted
time: 1932ms
memory: 74164kb

input:

1000000
1 2 1 3 5 6 2 6 9 7 4 5 4 13 7 8 14 10 9 13 3 22 10 8 25 14 19 20 27 16 18 28 15 20 23 32 26 19 28 11 35 37 24 25 11 35 37 23 46 31 51 45 48 12 47 16 24 36 49 40 60 12 38 22 47 63 62 27 66 60 43 65 62 33 75 41 64 68 29 69 18 30 75 63 85 40 56 86 59 77 51 72 91 31 77 56 38 61 50 99 57 80 55 5...

output:

989758826
392422866
207860708
905829009
642358070
424613204
728743757
313003726
190170136
595367701
117581599
589819381
992585502
290877247
955744494
98657684
27097502
522025243
116146660
850174377
263392388
270426742
473854645
463113359
900032196
645557621
564993634
86610697
302318274
218742784
625...

result:

ok all correct

Test #69:

score: 30
Accepted
time: 1910ms
memory: 74104kb

input:

1000000
1 2 1 2 3 6 4 5 3 9 6 12 12 11 10 16 16 4 19 10 5 8 21 13 11 19 18 14 21 8 17 20 29 17 24 34 27 15 28 18 7 41 24 39 45 14 23 26 37 23 13 7 44 30 46 40 37 35 40 47 44 56 34 22 26 48 29 50 22 31 61 60 63 36 38 41 77 78 67 53 51 58 72 27 66 85 31 69 52 76 86 88 9 72 89 91 39 32 96 69 99 60 67 8...

output:

939691576
270087967
398551701
460750962
320278285
122589796
422807899
50902446
879588248
703642426
529777004
320137444
853273231
476849438
731759413
700413620
609060292
107515742
617554628
526359280
901927256
527856879
435355989
819965641
308106130
72818288
886447397
704167120
314358236
764502424
24...

result:

ok all correct

Test #70:

score: 30
Accepted
time: 1946ms
memory: 74160kb

input:

1000000
1 2 1 2 5 4 4 6 9 3 6 11 12 7 10 11 16 7 16 8 12 14 17 10 24 14 15 17 5 15 25 30 27 33 29 18 24 37 20 20 25 35 39 13 44 18 38 48 42 8 40 41 41 22 26 33 37 53 57 28 38 9 13 52 63 58 45 58 43 56 39 53 66 35 29 60 26 64 56 19 3 72 75 51 34 49 75 72 81 46 70 77 50 85 83 92 50 78 48 57 81 31 87 5...

output:

383876223
87291142
697610990
893654648
99298212
482017003
266553532
875966899
354573256
124295901
307087273
122001136
654284825
693472283
109217790
613732967
488047846
792183331
740795465
429164181
596655572
59192527
223841642
72951800
635181431
955643289
495630080
709217422
132967405
407166123
1318...

result:

ok all correct

Test #71:

score: 30
Accepted
time: 1951ms
memory: 74096kb

input:

1000000
1 1 3 2 3 2 4 7 5 10 10 6 4 11 5 8 17 17 9 18 12 16 21 24 9 8 22 19 14 11 27 24 26 31 20 31 15 38 32 36 32 14 39 35 42 40 12 44 41 36 6 43 40 27 35 45 15 57 16 29 52 37 46 28 23 56 50 67 49 7 21 71 44 70 58 29 58 37 19 42 66 50 20 18 54 86 84 45 22 64 23 43 82 79 13 77 97 46 64 100 55 55 13 ...

output:

582349369
473327294
459477094
449187099
4208838
454373588
721173656
795320261
757619240
334800448
756311332
563915859
360044024
279601093
15619971
745802699
104339322
467854613
981160979
190213874
712716512
809869630
381167195
170529655
487888563
551633941
522725924
378411543
686011249
944643034
426...

result:

ok all correct

Test #72:

score: 30
Accepted
time: 1946ms
memory: 73988kb

input:

1000000
1 1 2 2 5 6 3 4 9 9 7 12 10 7 12 5 16 18 17 11 6 8 17 24 10 26 3 21 28 29 23 28 4 16 13 31 27 29 24 11 27 19 21 33 40 46 26 13 23 31 35 44 37 52 34 54 33 46 42 30 51 48 57 52 34 35 20 43 45 14 20 53 72 53 40 30 15 41 56 66 8 57 14 38 84 80 41 78 58 75 69 90 58 36 93 61 78 81 45 87 95 80 49 2...

output:

553157904
602750160
249802084
989864943
51260138
270291998
500415106
152375685
393408657
495532630
343990114
365426907
132914255
415012218
975083327
518052793
995661124
587172808
78983230
984900044
280725837
926841842
629092240
780599718
214472739
174846700
673411652
356694849
830892678
745465027
83...

result:

ok all correct

Test #73:

score: 30
Accepted
time: 1950ms
memory: 74164kb

input:

1000000
1 1 3 2 4 4 7 5 5 9 2 7 3 9 15 14 16 8 17 19 21 20 10 20 8 16 21 22 26 28 18 19 11 32 30 34 24 35 26 35 32 39 38 38 25 15 14 46 17 41 46 23 34 48 11 49 54 30 39 44 27 55 12 36 18 24 61 57 45 62 23 59 47 48 69 50 12 70 36 71 73 57 72 80 50 53 52 78 77 27 59 85 66 53 80 76 51 42 85 13 22 29 45...

output:

930837522
874242280
779159954
230178465
358135420
435108819
126453091
971820094
899871140
170780424
410941701
88218777
520324844
753276415
861284468
297523687
515131203
339155469
963228706
502887458
647308287
819505193
945024153
590218863
283859745
742878093
135034305
831378737
861880079
475845937
9...

result:

ok all correct

Test #74:

score: 30
Accepted
time: 1910ms
memory: 74104kb

input:

1000000
1 2 2 1 5 4 6 7 9 8 10 10 6 14 4 5 12 16 15 19 14 7 18 20 18 13 22 11 28 22 27 26 21 33 25 29 13 19 17 38 35 29 36 24 35 42 44 36 11 41 42 23 34 40 55 39 41 3 40 15 24 60 31 51 12 38 51 52 39 27 58 47 53 53 74 31 58 73 60 68 25 43 63 66 55 37 76 65 70 80 61 75 87 61 73 90 77 83 16 32 47 102 ...

output:

700645453
307681413
389410778
807546743
908262184
631463146
413517827
378315557
159211696
429522633
466475068
410844207
286852143
688471134
138236704
495031002
209202855
356519399
163297609
974027138
746606004
651220283
403777282
243834590
494626207
63193487
872446106
705367194
634393016
987924424
3...

result:

ok all correct

Test #75:

score: 30
Accepted
time: 1892ms
memory: 74092kb

input:

1000000
1 2 2 4 1 6 6 7 3 7 3 12 4 13 5 5 15 15 18 19 18 16 21 20 8 26 23 25 25 10 22 22 27 11 19 8 10 26 29 37 32 16 33 29 21 36 32 20 30 27 45 37 24 52 23 50 38 39 33 52 55 60 31 40 61 47 38 44 14 61 48 54 43 72 70 41 73 12 79 69 49 17 13 30 51 77 17 11 58 80 91 69 35 34 71 34 54 83 74 75 62 57 67...

output:

170652372
437372204
877740954
306078560
168986759
417729276
829887323
211863573
726341898
306127020
288648294
351545406
735172866
35277771
289965197
690220310
566286466
118499866
38982936
496853144
642247065
978868341
338192866
454306969
729583333
127852713
916119868
272173867
338857258
169632874
19...

result:

ok all correct

Test #76:

score: 30
Accepted
time: 1922ms
memory: 74164kb

input:

1000000
1 2 3 3 2 4 6 7 7 8 6 1 13 5 9 11 8 11 16 15 9 19 21 19 14 21 16 12 17 22 30 32 15 22 33 14 13 20 26 18 10 42 36 34 4 27 27 29 26 45 50 50 25 46 53 24 24 41 54 10 20 18 33 44 23 36 5 63 32 65 70 39 52 45 57 58 58 41 75 51 47 67 57 31 25 29 38 81 71 61 53 65 55 61 17 70 73 77 71 94 87 62 64 8...

output:

743666168
187563892
611344118
215149766
198953410
200503702
405692720
684390242
340940837
93509131
715932581
659131190
383524706
628193586
393175754
244347980
131376137
226995034
963112455
488742395
834774230
430512463
908921446
837945594
679472220
349245334
815440200
699624112
249011494
523541709
8...

result:

ok all correct

Test #77:

score: 30
Accepted
time: 1941ms
memory: 74164kb

input:

1000000
1 1 2 3 3 2 6 5 8 4 9 9 5 13 8 14 6 16 13 16 10 21 17 24 23 25 24 20 20 4 17 31 23 31 26 29 22 27 10 39 18 11 34 26 33 35 32 46 7 12 21 22 39 25 38 18 32 42 44 46 7 48 15 63 62 12 59 57 49 43 52 14 53 37 72 57 49 66 43 55 67 51 41 44 80 55 37 61 88 70 52 89 40 40 80 73 63 75 67 75 65 93 77 7...

output:

5682824
500178271
930219512
325777491
526252587
364660630
715796977
661664179
825446483
353517059
587872133
482106145
145219684
319403134
75195296
985522907
589442488
110682554
19698576
816469516
115710286
144291761
28507260
426911102
130161060
218726919
822424268
987039229
542593635
267191025
41349...

result:

ok all correct

Test #78:

score: 30
Accepted
time: 1448ms
memory: 152220kb

input:

1000000
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 ...

output:

178233829
766686767
281747303
687871177
936825299
404213876
322782339
652280006
307711708
367017646
359596735
531355648
717716814
13180532
313800835
20037394
735551888
568161516
684894649
644080970
924759754
667412845
993082727
814742884
292619948
415884347
496353547
824973183
65461822
837644555
278...

result:

ok all correct

Subtask #4:

score: 0
Wrong Answer

Test #79:

score: 0
Wrong Answer
time: 146ms
memory: 33188kb

input:

100000
1 1 3 4 5 6 7 8 9 10 9 12 13 14 15 14 12 8 19 20 21 20 19 24 24 26 26 28 29 26 31 26 33 34 26 36 36 38 39 40 41 36 4 44 45 46 47 47 49 44 51 52 53 54 53 52 57 58 59 60 61 61 63 61 65 66 67 67 69 70 69 72 59 74 74 76 76 78 79 78 81 82 83 84 85 82 87 87 58 90 91 92 93 91 95 51 97 98 99 99 101 1...

output:

736079324
657978221
595430141
440220745
849109682
291128321
127967213
916169355
473854641
262093747
675127246
942295678
513318668
117018684
40656034
777510525
834413159
623705754
678773095
899648692
551558006
117893600
891440155
904413463
37014957
664482432
944982499
639073421
725783142
900552661
26...

result:

wrong output format Extra information in the output file