QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#688516 | #1288. Tokens on the Tree | konata2828 | AC ✓ | 17ms | 8624kb | C++17 | 1.7kb | 2024-10-30 10:24:14 | 2024-10-30 10:24:15 |
Judging History
answer
// Hydro submission #6720c77337be2064ac9890c6@1730255052009
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,fa[200001],siz[200001],maxn[200001][3],f[200001];
inline void update(int u,int val){
if(val>maxn[u][0])maxn[u][2]=maxn[u][1],maxn[u][1]=maxn[u][0],maxn[u][0]=val;
else if(val>maxn[u][1])maxn[u][2]=maxn[u][1],maxn[u][1]=val;
else if(val>maxn[u][2])maxn[u][2]=val;
}
inline int sum(int l,int r){
return 1ll*(l+r)*(r-l+1)/2%mod;
}
int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
maxn[i][0]=maxn[i][1]=maxn[i][2]=f[i]=0;
siz[i]=1;
}
for(int i=2;i<=n;i++)scanf("%d",fa+i);
for(int i=n;i>=1;i--){
update(i,n-siz[i]);
if(fa[i])update(fa[i],siz[i]),siz[fa[i]]+=siz[i];
}
long long answer=0;
for(int i=2;i<=n;i++){
int u=i,v=fa[i];
if(maxn[u][0]<maxn[v][0])answer+=1ll*sum(maxn[u][0]+1,maxn[v][0])*sum(1,n-siz[u])%mod;
else answer+=1ll*sum(maxn[v][0]+1,maxn[u][0])*sum(1,siz[u])%mod;
}
for(int i=1;i<=n;i++)f[maxn[i][1]]=max(f[maxn[i][1]],maxn[i][2]);
for(int i=n-1;i>=1;i--)f[i]=max(f[i],f[i+1]);
int minn=n;
for(int i=1;i<=n;i++)minn=min(minn,maxn[i][0]);
for(int i=1;i<=minn;i++){
int x=min(i,f[i]);
answer+=1ll*i*sum(1,x)%mod;
answer+=2ll*i*sum(x+1,i)%mod;
}
answer=2*answer%mod;
for(int i=1;i<=minn;i++)
answer-=(i<=f[i]?1ll:2ll)*i*i%mod;
printf("%lld\n",(answer%mod+mod)%mod);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 8044kb
input:
2 5 1 2 3 3 10 1 2 3 4 3 6 3 8 2
output:
71 989
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 15ms
memory: 5952kb
input:
33327 10 1 2 3 4 5 2 7 8 2 7 1 2 3 4 5 2 8 1 2 3 4 5 3 1 2 1 7 1 2 3 3 3 1 5 1 2 2 1 5 1 2 3 1 2 1 4 1 2 2 8 1 2 3 4 5 5 4 9 1 2 3 1 5 6 7 8 5 1 1 3 4 8 1 2 3 3 5 5 5 8 1 2 2 2 1 6 1 6 1 2 3 2 5 7 1 2 3 4 3 2 5 1 2 3 3 4 1 1 1 6 1 1 3 4 4 3 1 2 10 1 2 1 4 5 5 7 7 9 2 1 3 1 2 6 1 1 3 4 5 7 1 2 3 1 5 ...
output:
981 253 421 2 251 71 70 2 31 423 660 70 419 419 141 255 71 31 141 10 997 2 10 140 252 10 71 2 2 675 423 1007 71 70 140 429 30 667 10 945 655 70 661 10 10 70 31 255 141 71 255 669 30 252 2 30 419 255 661 427 10 421 2 659 141 993 30 141 417 10 2 423 141 30 667 675 417 71 421 255 10 140 675 2 30 2 31 3...
result:
ok 33327 tokens
Test #3:
score: 0
Accepted
time: 17ms
memory: 3832kb
input:
33235 9 1 1 3 3 5 6 5 8 7 1 1 3 4 5 1 5 1 2 1 4 4 1 1 3 9 1 1 3 3 5 6 7 6 5 1 2 3 4 2 1 8 1 2 3 3 5 6 5 5 1 2 3 3 3 1 2 4 1 2 3 9 1 1 3 4 1 6 6 8 2 1 9 1 1 3 4 5 6 4 8 4 1 2 3 5 1 2 3 4 8 1 2 3 1 1 6 7 6 1 2 3 2 5 4 1 2 3 6 1 2 3 4 3 4 1 2 3 3 1 2 2 1 10 1 2 1 4 4 1 7 7 9 3 1 1 5 1 1 3 3 10 1 1 3 3 ...
output:
675 253 70 30 667 70 2 427 71 10 30 667 2 669 30 70 421 141 30 141 30 10 2 1007 10 71 1003 253 2 10 429 253 955 10 2 10 959 663 253 141 252 423 30 655 141 2 417 2 663 251 140 997 661 2 253 1005 71 1005 253 31 30 667 661 70 1028 2 10 653 71 667 141 661 661 71 141 141 2 10 999 140 2 251 415 10 2 261 2...
result:
ok 33235 tokens
Test #4:
score: 0
Accepted
time: 14ms
memory: 7944kb
input:
13351 16 1 2 2 4 2 6 7 7 9 7 7 12 12 6 1 11 1 2 3 4 2 6 7 8 6 10 18 1 2 3 4 5 4 7 7 7 4 1 12 13 14 15 15 14 14 1 2 3 3 5 6 7 6 9 5 3 12 2 10 1 2 3 1 5 6 7 6 5 15 1 2 2 4 5 4 7 8 9 9 9 9 13 4 16 1 2 3 4 4 6 3 8 9 10 11 12 11 1 15 10 1 1 3 4 5 6 7 8 7 17 1 2 3 4 5 5 7 8 5 10 11 12 13 12 11 16 19 1 2 3...
output:
5847 1451 9557 3615 997 4587 6232 991 7694 12088 14582 11874 7716 2733 14269 985 1421 6128 1423 3631 14190 1413 3661 999 14740 14810 13876 1993 3610 1437 6177 14772 2457 13911 981 11496 13667 2725 2780 4785 14241 1967 6225 4625 6085 981 1959 1439 6258 11185 11671 1971 2011 9745 2631 11999 3535 9803 ...
result:
ok 13351 tokens
Test #5:
score: 0
Accepted
time: 10ms
memory: 5940kb
input:
13295 18 1 1 3 4 5 1 7 8 8 10 11 12 13 14 15 13 1 13 1 2 3 4 5 1 7 8 7 10 11 12 16 1 1 1 4 5 6 5 8 8 10 11 11 13 13 13 18 1 2 3 2 5 6 7 7 7 5 11 11 13 11 1 16 17 15 1 2 3 4 5 2 7 8 8 10 11 12 11 2 15 1 2 2 4 5 6 2 8 8 10 1 12 13 13 13 1 2 3 2 5 6 6 8 8 10 5 12 10 1 2 2 4 5 6 7 8 6 16 1 2 3 2 5 6 7 8...
output:
9657 2739 6153 9915 4745 4748 2771 993 6184 1405 4659 2046 4815 997 7656 2003 9481 8963 7737 14226 9753 2013 1431 5619 9675 6185 949 1474 2721 4726 3675 6043 2023 11988 3581 999 2017 14397 7582 1415 14074 1421 4787 1429 9363 997 1411 2763 7701 3377 6072 2778 14722 12033 2046 9435 1421 4542 4745 7717...
result:
ok 13295 tokens
Test #6:
score: 0
Accepted
time: 10ms
memory: 5940kb
input:
13322 20 1 2 3 4 2 6 7 8 9 9 11 12 6 14 14 16 17 18 18 14 1 1 3 4 5 6 7 8 9 10 11 11 9 18 1 2 2 4 5 6 6 1 9 10 10 9 13 13 15 16 17 12 1 1 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 5 4 1 9 10 11 15 1 2 3 4 5 4 7 8 8 10 1 12 13 12 16 1 2 2 4 5 6 5 8 9 10 10 12 13 9 15 20 1 2 3 3 5 2 1 8 9 10 8 12 12 14 15 16 1...
output:
14911 3643 9780 2002 2005 4781 6203 14768 6121 14794 3681 4773 7850 3688 7821 9785 4763 6192 12071 6127 12055 999 4787 4761 2015 2023 9734 1445 3685 14836 12027 2038 9727 1430 4775 3682 2005 1431 9852 3649 1005 991 9777 12270 2737 4761 2029 2003 3647 1470 14690 2015 2003 6258 1431 4798 2040 2056 275...
result:
ok 13322 tokens
Test #7:
score: 0
Accepted
time: 13ms
memory: 6008kb
input:
13380 17 1 1 3 4 4 6 7 7 9 9 6 12 12 14 14 3 15 1 2 2 4 5 5 4 8 8 10 11 11 10 1 13 1 2 3 3 5 5 7 7 2 10 10 1 15 1 2 2 4 5 6 6 5 9 10 10 9 4 1 13 1 2 3 3 2 6 6 8 9 9 8 1 9 1 2 2 1 5 6 6 5 17 1 1 3 4 4 6 6 8 9 9 11 11 8 3 15 15 13 1 1 3 3 5 5 7 8 9 9 8 7 11 1 2 3 4 5 5 4 3 2 1 15 1 2 3 4 5 5 4 8 8 10 ...
output:
8031 4838 2767 4838 2767 665 7861 2771 1451 4838 12128 7916 7848 1451 2767 7848 12148 12132 2771 7880 2784 12139 4880 7860 2759 1447 1476 1451 4838 2771 7932 1447 2767 1447 1447 4827 4827 8031 1451 669 7872 12134 8031 1451 4838 1447 1476 2767 1451 7856 7860 7865 12164 7861 2808 669 12286 4827 1451 4...
result:
ok 13380 tokens
Test #8:
score: 0
Accepted
time: 14ms
memory: 8044kb
input:
13313 20 1 2 3 4 5 6 6 6 6 6 5 5 4 3 3 2 2 2 2 14 1 2 3 3 3 3 3 3 3 2 2 2 2 14 1 2 3 3 3 3 2 2 2 2 2 1 1 20 1 2 3 4 4 4 4 4 3 3 3 3 3 3 2 16 17 16 2 18 1 2 3 4 4 4 4 4 4 3 3 3 2 2 2 1 1 10 1 2 2 4 4 2 2 2 2 11 1 2 3 3 2 2 2 2 2 2 20 1 1 3 4 5 5 5 4 4 4 3 3 3 3 3 1 1 1 1 11 1 2 2 4 4 4 2 2 2 2 17 1 2...
output:
13999 3041 3179 12735 8865 871 1193 13019 1261 6851 8111 12825 3921 5443 1261 5559 4899 6809 5591 5899 3041 1193 913 8449 5515 7127 2329 2773 3323 913 5783 1301 1755 8469 4363 11087 871 2481 13549 2481 2933 10385 7271 8585 871 5591 5515 5505 12603 3921 913 2933 8445 2297 2359 13353 13809 2421 2297 9...
result:
ok 13313 tokens
Test #9:
score: 0
Accepted
time: 14ms
memory: 6000kb
input:
13347 11 1 2 3 3 5 2 7 7 2 10 19 1 2 3 4 5 6 7 8 8 6 11 6 5 14 14 4 17 3 13 1 2 3 4 5 6 6 6 5 10 2 1 10 1 2 3 4 2 6 7 6 9 12 1 2 3 4 4 4 4 2 9 9 11 10 1 2 3 3 3 2 1 8 1 14 1 2 3 2 1 6 7 8 9 6 11 6 1 20 1 2 3 4 5 6 7 5 9 9 5 12 12 4 3 2 1 1 19 10 1 2 3 4 5 6 3 8 3 16 1 2 3 2 5 6 7 8 9 7 2 12 2 14 15 ...
output:
1417 11986 2733 1005 1963 991 3605 14354 979 5803 14458 2571 7705 2703 1442 4672 6047 1857 2001 2042 1983 1949 3720 7821 3483 3627 3619 3591 5981 3599 2692 3633 3619 9435 5961 13871 7644 5999 987 1935 9540 7738 6137 4691 6136 987 1411 4817 7745 1005 9682 9211 11581 3605 14765 14527 1005 985 4519 885...
result:
ok 13347 tokens
Test #10:
score: 0
Accepted
time: 14ms
memory: 7916kb
input:
13373 13 1 2 3 4 5 6 7 1 9 10 11 12 10 1 1 1 4 5 6 6 8 8 19 1 2 3 4 4 6 7 8 9 10 11 12 13 13 15 15 17 8 14 1 2 3 4 5 5 5 8 3 10 2 2 1 14 1 2 3 4 3 1 7 8 8 10 7 12 12 17 1 2 2 4 1 6 7 7 9 10 11 12 11 14 14 16 11 1 2 3 4 5 6 7 8 1 10 20 1 2 3 4 5 5 7 7 9 10 9 12 13 13 15 16 17 16 19 13 1 2 3 4 5 1 7 8...
output:
2730 995 12009 3605 3690 7793 1430 14761 2766 1441 4814 4779 11891 7662 11802 7752 7854 7789 3661 9792 3671 4789 3655 2019 6090 2717 14742 3621 7809 6120 1437 997 1001 991 2786 3665 14797 11970 3655 12237 11973 14726 14740 9729 12239 991 6120 7752 9690 9729 12068 12172 14679 1421 11909 12009 990 969...
result:
ok 13373 tokens
Test #11:
score: 0
Accepted
time: 13ms
memory: 5952kb
input:
13319 20 1 2 3 4 5 6 7 8 9 10 4 12 13 14 15 16 1 18 19 12 1 2 3 4 1 6 7 8 1 10 11 15 1 2 3 4 5 6 7 8 1 10 11 12 13 14 12 1 2 3 4 5 6 7 8 9 10 1 20 1 2 3 4 5 6 7 8 9 10 11 5 13 14 15 16 17 1 19 10 1 2 3 4 5 6 7 1 9 10 1 2 3 4 5 6 7 8 1 13 1 2 3 4 5 6 1 8 9 10 11 12 12 1 2 3 4 5 6 7 8 5 10 11 11 1 2 3...
output:
15071 2038 4760 2002 15071 990 990 2730 2038 1466 6076 990 2730 4860 6345 1466 9550 9690 1466 11970 14455 4860 2830 3740 2038 12411 3740 7977 7752 2830 3740 11770 4860 2730 3640 6345 3640 9690 2038 9915 2002 9690 9690 3740 12411 4860 3640 9550 6345 4760 12411 11770 14455 14455 4860 3740 11970 12411 ...
result:
ok 13319 tokens
Test #12:
score: 0
Accepted
time: 13ms
memory: 8040kb
input:
1331 119 1 2 3 4 5 6 4 8 9 10 11 12 13 14 13 16 12 18 11 20 21 22 23 21 25 26 27 28 21 30 21 21 33 33 35 36 37 38 21 40 41 41 43 41 45 40 47 48 47 50 51 47 20 54 55 56 57 10 10 60 61 62 62 64 65 66 67 67 69 70 69 69 73 66 75 76 75 78 64 80 81 82 80 80 85 86 86 88 86 86 91 91 93 94 91 85 10 98 9 9 10...
output:
16570757 9751684 123915187 58766083 63371870 12616766 88554035 97237846 35332099 114425639 12486970 11650577 124781347 14059981 113039442 31039918 106130498 73388159 103405796 66238404 46262682 82979628 40369324 92671328 62153167 114203511 112763901 9420497 45655957 80789465 24795492 31890282 692318...
result:
ok 1331 tokens
Test #13:
score: 0
Accepted
time: 10ms
memory: 7988kb
input:
1338 132 1 2 1 1 1 6 6 8 9 10 10 12 12 14 15 15 17 18 18 18 21 21 23 24 25 25 24 14 29 30 31 32 33 34 34 29 37 38 39 40 39 42 43 44 42 46 47 47 37 50 51 51 53 54 54 50 57 58 59 10 61 62 63 63 65 66 66 68 65 70 71 72 63 74 74 76 77 77 77 80 80 80 74 84 62 61 87 87 89 89 91 91 93 94 94 91 97 98 99 99 ...
output:
25981043 9667467 9777460 104463661 84423870 100952223 120940778 70267377 27395963 89523514 12724181 34579206 31916003 76525894 12392832 97032849 99848041 91402366 29488706 12739021 123699407 8533622 8859547 47470430 11653010 32510633 10770300 8169176 27806488 10278985 76093584 64790147 58271117 3647...
result:
ok 1338 tokens
Test #14:
score: 0
Accepted
time: 13ms
memory: 5820kb
input:
1343 110 1 1 3 3 5 6 7 8 5 10 11 12 10 14 15 16 17 18 18 20 21 21 17 24 25 26 25 28 29 30 24 32 33 34 35 36 37 38 34 32 41 41 43 44 45 46 47 43 49 49 51 52 53 54 54 56 57 58 59 60 61 61 63 64 65 66 67 68 69 70 71 68 65 74 75 76 77 76 79 80 81 82 83 82 85 85 87 80 89 90 91 92 93 75 95 96 97 96 99 100...
output:
12543826 88833773 21567936 83147997 25934028 55722696 95232474 105743908 120260110 77770233 12068943 18328202 9624959 77829645 33611013 95344758 20788220 19529396 110467417 65984404 69169230 26665785 35601552 54236888 45386148 11205649 46680804 81396456 23674568 29988000 62818286 12978116 105646968 ...
result:
ok 1343 tokens
Test #15:
score: 0
Accepted
time: 10ms
memory: 5956kb
input:
1333 189 1 2 3 4 4 6 6 3 9 10 11 11 13 14 14 16 16 13 19 19 10 22 22 9 25 26 26 25 29 29 31 31 33 34 34 33 37 38 39 40 41 42 42 44 44 41 47 48 49 49 51 51 53 54 54 53 48 58 59 59 58 47 63 63 65 66 67 67 66 70 71 71 70 74 74 76 77 78 79 79 81 81 83 84 85 85 84 88 88 83 91 92 93 94 95 96 97 98 99 99 1...
output:
108457171 18325621 70323460 12166445 83793668 13034239 22456588 30486520 100325839 63438697 33754379 26857907 13239171 60349855 58356080 91524655 18632979 36065812 10473304 35941831 18428716 66924396 124011639 23822792 22317643 105154787 134455007 10549871 88294375 66619287 33701553 33839873 8815011...
result:
ok 1333 tokens
Test #16:
score: 0
Accepted
time: 13ms
memory: 5820kb
input:
1332 135 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 15 15 15 15 14 14 13 13 12 11 11 10 10 9 8 7 7 7 7 6 4 2 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 66 66 66 65 65 65 64 64 64 64 64 62 62 61 61 61 60 59 59 58 57 57 57 57 56 56 56 56 55 54 54 54 54 53 53 53 52 ...
output:
27698821 24653403 105376259 132732731 60213695 99283489 72661699 17708775 81717741 50447263 11248179 12645067 101658305 61182141 112911305 89398061 56691007 103251571 51581179 133059881 58610119 108480757 39830777 37690959 69355153 25285779 12608465 9074781 74719941 45317631 23580723 92554317 570849...
result:
ok 1332 tokens
Test #17:
score: 0
Accepted
time: 13ms
memory: 5960kb
input:
1336 181 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 66 66 64 64 61 61 61 60 60 59 56 78 79 80 54 82 54 84 85 53 53 53 52 50 49 92 49 48 48 47 44 98 44 44 ...
output:
90211839 10958265 131485835 18700896 16896442 55261824 22361006 31420499 28852017 40433216 23931053 19357872 58969751 19275823 12770683 87396520 51842060 79737509 34140018 16797699 9352855 50022383 8756253 42409975 37316785 64832429 51047901 12263637 131360167 96470375 78179380 88344183 16977564 902...
result:
ok 1336 tokens
Test #18:
score: 0
Accepted
time: 12ms
memory: 5948kb
input:
1329 126 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 19 23 24 18 16 27 28 29 29 12 32 10 8 8 6 3 3 2 40 1 42 43 43 45 45 47 48 49 50 50 52 53 54 55 54 57 57 59 60 59 62 63 64 65 66 67 68 66 70 71 72 73 73 75 76 77 76 79 80 81 81 83 84 84 86 87 83 89 90 91 92 92 92 95 96 97 98 99 100 101 10...
output:
21391199 10753109 33481764 86660175 24165570 37365559 75235917 18801722 121724330 31642771 23433280 20116198 72170246 20058340 12005668 109937208 48751666 16504931 119445146 61122936 12471221 49938026 35359610 18175749 105394183 13379652 9226286 11126502 40520550 13896161 45156529 46260060 12917640 ...
result:
ok 1329 tokens
Test #19:
score: 0
Accepted
time: 12ms
memory: 6004kb
input:
1310 104 1 2 3 4 5 6 7 7 7 7 6 12 12 12 12 6 17 17 17 17 6 22 22 22 22 5 27 28 28 28 28 27 33 33 33 33 27 38 38 38 38 27 43 43 43 43 4 48 49 49 49 49 48 54 54 54 54 48 59 59 59 59 48 64 64 64 64 4 69 70 70 70 70 69 75 75 75 75 69 69 4 82 82 82 82 3 87 87 87 87 3 92 92 92 92 3 97 97 97 97 2 2 2 115 1...
output:
8869903 15344218 52676612 12174201 105026651 17592770 19180031 69405068 94013288 52832111 21578301 23874673 39405236 95867563 50355267 16589097 127574330 29162996 38350372 46218648 50355267 74519489 61062819 17509607 51580161 104245758 13516914 10323344 35325200 32590178 33416084 100357664 17509607 ...
result:
ok 1310 tokens
Test #20:
score: 0
Accepted
time: 12ms
memory: 5876kb
input:
1332 117 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 4 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 4 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 1 92 93 94 95 96 97 98 99 100 10...
output:
15413065 19399366 7499601 8589425 23482270 28286870 41403021 15122310 21243191 14640402 40722236 10105514 15829500 54827640 29186509 9564952 88782560 42772352 27718425 7167573 7499601 7882537 8371064 73480429 7312070 11589721 28987960 23846121 10107954 7438865 20512609 61098720 12401880 44835468 956...
result:
ok 1332 tokens
Test #21:
score: 0
Accepted
time: 16ms
memory: 6836kb
input:
4 50000 1 2 3 4 5 6 6 8 9 9 9 12 12 14 14 16 16 18 16 14 21 14 23 12 25 26 27 12 29 29 8 8 33 34 33 36 37 38 39 40 41 41 43 44 45 37 36 48 49 50 51 50 49 33 55 55 8 58 59 59 61 62 63 64 65 66 66 63 69 70 71 72 63 74 75 75 63 78 79 79 63 63 63 62 62 58 58 8 89 90 91 89 93 94 95 89 97 98 99 100 100 10...
output:
373903080 660672651 886713244 424495455
result:
ok 4 tokens
Test #22:
score: 0
Accepted
time: 15ms
memory: 8180kb
input:
4 50000 1 1 3 4 4 3 7 8 9 10 10 12 13 14 15 16 14 18 19 20 21 22 23 24 23 22 27 28 29 30 31 29 33 33 19 36 36 19 1 40 41 41 43 43 45 46 46 48 49 50 49 52 52 54 55 49 57 58 59 60 61 62 63 63 65 66 66 68 68 65 71 63 63 74 74 76 77 78 77 80 76 82 82 82 85 85 87 88 89 90 91 92 89 94 85 96 96 98 99 99 98...
output:
536955498 247162896 467816003 935101132
result:
ok 4 tokens
Test #23:
score: 0
Accepted
time: 15ms
memory: 8080kb
input:
4 50000 1 2 3 3 5 6 7 7 9 10 10 12 12 9 15 16 15 18 18 20 21 22 23 20 25 25 27 28 29 28 31 32 33 32 35 36 37 38 39 39 41 38 43 43 45 46 47 48 49 50 50 48 47 54 45 56 57 58 59 60 60 58 56 64 65 66 67 66 64 70 70 72 73 73 75 76 75 78 79 80 81 82 83 84 85 82 80 88 89 88 91 92 93 94 95 96 93 98 99 98 10...
output:
895907800 892131148 721383716 622521650
result:
ok 4 tokens
Test #24:
score: 0
Accepted
time: 7ms
memory: 6676kb
input:
4 49999 1 2 3 4 4 6 6 8 9 10 10 12 13 13 15 15 12 9 8 3 2 22 22 1 25 26 26 28 29 29 31 32 33 34 35 36 36 35 34 33 41 41 43 43 32 31 28 48 49 50 51 51 53 54 55 56 56 55 54 60 60 62 63 63 62 53 67 67 50 49 71 71 73 73 48 76 77 78 79 79 81 81 83 84 85 85 87 88 89 89 88 92 92 94 95 95 97 97 94 100 100 8...
output:
422337347 804576279 68922823 463411927
result:
ok 4 tokens
Test #25:
score: 0
Accepted
time: 15ms
memory: 6828kb
input:
4 50000 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:
987722357 804692726 193354538 55346543
result:
ok 4 tokens
Test #26:
score: 0
Accepted
time: 7ms
memory: 6708kb
input:
4 50000 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:
515794214 169502180 161905459 758084321
result:
ok 4 tokens
Test #27:
score: 0
Accepted
time: 11ms
memory: 6528kb
input:
4 50000 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:
812345866 488809075 429574271 204059999
result:
ok 4 tokens
Test #28:
score: 0
Accepted
time: 11ms
memory: 6588kb
input:
4 50000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 30 34 34 29 37 38 38 37 41 41 28 44 45 46 46 45 49 49 44 52 53 53 52 56 56 27 59 60 61 62 62 61 65 65 60 68 69 69 68 72 72 59 75 76 77 77 76 80 80 75 83 84 84 83 87 87 26 90 91 92 93 94 94 93 97 97 92 100 ...
output:
366775595 665527557 953383394 953383394
result:
ok 4 tokens
Test #29:
score: 0
Accepted
time: 13ms
memory: 7920kb
input:
4 50000 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:
187953489 1936782 922649750 211559091
result:
ok 4 tokens
Test #30:
score: 0
Accepted
time: 12ms
memory: 7608kb
input:
2 99996 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:
748357479 266466936
result:
ok 2 tokens
Test #31:
score: 0
Accepted
time: 15ms
memory: 8120kb
input:
2 99999 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:
649496962 515932762
result:
ok 2 tokens
Test #32:
score: 0
Accepted
time: 15ms
memory: 7052kb
input:
2 99997 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:
909371559 733461413
result:
ok 2 tokens
Test #33:
score: 0
Accepted
time: 16ms
memory: 8572kb
input:
1 200000 1 2 3 4 5 6 7 8 6 10 11 12 13 14 15 16 17 18 19 20 19 18 23 24 18 26 26 28 18 15 31 32 33 34 34 31 31 13 39 40 41 42 43 44 45 46 46 44 49 49 42 52 42 54 41 56 57 40 39 60 61 62 63 64 64 66 66 68 68 70 71 72 73 74 75 76 77 74 71 71 70 70 68 66 85 86 87 88 89 90 89 88 66 63 95 95 62 98 98 100...
output:
148306941
result:
ok "148306941"
Test #34:
score: 0
Accepted
time: 12ms
memory: 8624kb
input:
1 200000 1 1 3 4 5 6 5 8 8 10 11 12 5 14 15 15 17 15 19 14 21 22 4 24 25 26 26 28 29 30 29 32 33 33 32 36 37 38 39 39 41 41 43 41 45 46 47 48 48 45 51 52 53 53 55 56 57 56 59 52 61 61 61 64 65 66 67 67 66 66 71 72 73 74 75 74 77 78 79 79 81 81 77 84 85 86 85 88 89 88 88 92 93 93 95 95 97 98 95 100 1...
output:
940424267
result:
ok "940424267"
Test #35:
score: 0
Accepted
time: 16ms
memory: 8444kb
input:
1 200000 1 1 3 4 3 6 7 8 9 10 9 7 13 13 15 16 15 18 19 20 21 22 19 24 25 25 27 28 29 30 29 32 33 33 35 36 37 38 39 40 41 40 43 35 45 46 45 48 49 50 51 52 53 53 55 56 57 58 59 57 61 62 63 62 65 66 67 68 69 70 71 72 73 74 70 76 76 78 79 80 81 79 83 84 85 86 87 88 89 85 91 83 93 94 95 95 97 98 98 100 1...
output:
309320185
result:
ok "309320185"
Test #36:
score: 0
Accepted
time: 12ms
memory: 8576kb
input:
1 199999 1 1 3 4 4 6 7 8 9 9 11 11 8 14 15 16 17 18 18 17 16 15 23 23 25 26 26 25 29 29 14 32 33 34 35 35 34 38 38 40 41 42 42 41 40 46 47 48 49 49 48 47 46 54 54 56 57 58 59 59 58 62 62 64 65 66 67 67 69 69 71 71 73 74 75 76 76 78 79 79 81 81 78 84 84 86 87 87 89 89 91 92 93 94 94 96 96 93 99 99 10...
output:
955804572
result:
ok "955804572"
Test #37:
score: 0
Accepted
time: 16ms
memory: 8504kb
input:
1 200000 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:
690798928
result:
ok "690798928"
Test #38:
score: 0
Accepted
time: 16ms
memory: 8528kb
input:
1 199997 1 1 3 1 5 6 7 6 5 1 11 12 13 14 15 11 17 18 19 20 21 22 23 23 25 26 27 25 29 30 31 32 33 34 35 36 37 38 39 40 41 39 43 39 35 46 47 48 49 50 51 51 50 48 55 47 46 58 58 60 60 46 46 64 64 66 34 68 69 70 71 68 33 74 74 32 77 78 79 80 81 79 31 31 85 86 87 86 89 90 91 90 93 86 85 96 97 98 99 98 9...
output:
7348617
result:
ok "7348617"
Test #39:
score: 0
Accepted
time: 12ms
memory: 8500kb
input:
1 199997 1 2 3 4 5 6 4 2 9 9 11 12 13 14 15 16 15 18 19 20 18 15 23 24 25 26 26 28 23 30 23 32 33 32 14 36 37 38 38 40 41 42 43 44 45 45 47 48 48 48 51 52 53 53 55 56 57 58 59 57 61 62 62 64 65 62 67 68 67 57 71 57 56 74 55 76 77 78 53 52 81 82 82 52 52 41 87 88 89 90 91 92 89 94 88 87 97 98 99 100 ...
output:
136628442
result:
ok "136628442"
Test #40:
score: 0
Accepted
time: 17ms
memory: 8504kb
input:
1 199998 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:
347377291
result:
ok "347377291"