QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#374886 | #2814. 不用找的树 | Ecec243 | AC ✓ | 2102ms | 46484kb | C++23 | 8.0kb | 2024-04-02 19:11:54 | 2024-04-02 19:11:55 |
Judging History
answer
#include<bits/stdc++.h>
using std::min;
typedef long long i64;
const int N=1.1e5+7,BN=1007,Bmax=1000;
#define F(i,n) for(int i=0;i<(n);++i)
#define F3(i,l,r) for(int i=(l);i<(r);++i)
#define clr(a,n) memset((a),0,sizeof((a)[0])*(n))
char ib[1<<23],*ip=ib,ob[1<<22],*op=ob;
int read(){
int x=0;
while(*ip<48)++ip;
while(*ip>47)x=x*10+*ip++-48;
return x;
}
void print(i64 x){
char ss[20];
int sp=0;
do ss[sp++]=x%10+48;while(x/=10);
while(sp)*op++=ss[--sp];
*op++=10;
}
void* operator new(size_t n){
static char* l=0,*r=0;
if(r<l+n){
int L=1<<24;
l=(char*)malloc(L),r=l+L,clr(l,L);
}
r-=n;
return r;
}
void operator delete(void*){}
int n,m,cur_q,B;
i64 ans[N];
std::vector<int>e[N];
int id[N],idp=0,bid[N],fa[N],sz[N],btm[N],q[N],ql,qr;
struct Query{
int d0,d1,d,id;
};
struct Block{
int idl,sz,top,btm,*fa,*ch,*dep[2],*dsum[2][2],md[2],*dc[2];
std::vector<Query>qs;
void cal_dsum(int d0,int d1){
int _md=md[d0];
int *D0=dep[d0],*D1=dep[d1];
int *DS=dsum[d0][d1]=new int[_md]();
F3(i,1,sz)DS[D0[i]]+=D1[i];
F3(i,1,_md)DS[i]+=DS[i-1];
}
void cal_dc(int d){
int _md=md[d];
int *D=dep[d];
int *DC=dc[d]=new int[_md]();
F3(i,1,sz)DC[D[i]]+=1;
F3(i,1,_md)DC[i]+=DC[i-1];
}
void bfs(int rt,int d,int *ed,int&ds0,int&ds1,int&dc){
clr(ed,sz);
if(d-dep[0][rt]>md[0]){
ds0=dsum[0][0][md[0]-1];
if(btm)ds1=dsum[0][1][md[0]-1];
dc=sz-1;
for(int i=sz-1;i;--i)ed[fa[i]]+=++ed[i];
return;
}
ql=qr=0;
for(ed[q[++qr]=rt]=1;ql!=qr&&d>0;--d){
for(int p=qr,w;ql!=p;){
w=q[++ql];
for(int i=ch[w];i<ch[w+1];++i)if(!ed[i])ed[q[++qr]=i]=1;
if(!ed[fa[w]])ed[q[++qr]=fa[w]]=1;
}
}
dc=qr-ed[0];
F3(i,1,sz)ds0+=dep[0][i]*ed[i];
if(btm)for(int i=1;i<sz;++i)ds1+=dep[1][i]*ed[i];
for(int i=sz-1;i;--i)ed[fa[i]]+=ed[i];
}
i64 cal(int*a,int*b){
i64 s=0;
F3(i,1,sz)s+=a[i]*b[i];
return s;
}
void offline(int d0,int d1);
void init(int _top,int _btm,int bp){
top=_top,btm=_btm;
_top[id]=idl=idp;
while(ql!=qr){
int w=q[++ql];
w[id]=++idp;
idp[bid]=bp;
if(w[::sz]>1)for(int u:w[e])q[++qr]=u;
}
sz=qr+1;
assert(sz<=Bmax);
fa=new int[sz]();
ch=new int[sz+1]();
int p=0;
F3(i,1,sz){
int f=fa[i]=q[i][::fa][id]-idl;
while(p<f)ch[++p]=i;
}
while(p<sz)ch[++p]=sz;
int *D0=dep[0]=new int[sz]();
F3(i,1,sz)D0[i]=D0[fa[i]]+1;
md[0]=D0[sz-1]+1;
cal_dc(0);
cal_dsum(0,0);
if(btm){
int *D1=dep[1]=new int[sz]();
ql=qr=0;
int rt=btm[id]-idl;
D1[q[++qr]=rt]=1;
while(ql!=qr){
int w=q[++ql],d=(w==rt?0:D1[w])+1;
for(int i=ch[w];i<ch[w+1];++i)if(!D1[i])D1[q[++qr]=i]=d;
if(!D1[fa[w]])D1[q[++qr]=fa[w]]=d;
}
D1[rt]=0;
md[1]=D1[q[qr]]+1;
cal_dc(1);
cal_dsum(0,1);
cal_dsum(1,0);
cal_dsum(1,1);
}
}
}bs[BN];
int bp=0;
void new_block(int _top,int _btm){
if(ql==qr)return;
q[0]=_top;
++bp;
bs[bp].init(_top,_btm,bp);
ql=qr=0;
}
void build_blocks(int w){
int s=0,d=0;
for(int x:e[w]){
build_blocks(x);
s+=sz[x];
if(btm[x]){
btm[w]=btm[x];
++d;
}
}
if(s>=B||d>=2||!w){
btm[w]=w;
s=d=0;
std::sort(e[w].begin(),e[w].end(),[](int a,int b){return sz[a]<sz[b];});
for(int x:e[w]){
if(s>=B||(btm[x]&&d)){
new_block(w,d);
s=d=0;
}
if(!d)d=btm[x];
q[++qr]=x;
s+=sz[x];
}
new_block(w,d);
sz[w]=1;
}else sz[w]=1+s;
}
namespace BlockTree{
int *fa,*ch,*cr,*d01;
#define fore(w,i) for(int i=cr[w],i##_=cr[(w)+1];i<i##_;++i)
void build(){
build_blocks(0);
assert(bp<=Bmax);
fa=new int[bp+1]();
ch=new int[bp+1]();
cr=new int[bp+2]();
d01=new int[bp+1]();
for(int i=1;i<=bp;++i){
Block&B=bs[i];
if(B.btm)d01[i]=B.dep[0][B.btm[id]-B.idl];
for(int j=i+1;j<=bp;++j)if(bs[j].btm==bs[i].top){
++cr[fa[i]=j];
break;
}
}
for(int i=1;i<=bp+1;++i)cr[i]+=cr[i-1];
for(int i=1;i<bp;++i)ch[--cr[fa[i]]]=i;
}
struct info{
i64 ds,sz;
void add(const info&i,int d){
ds+=i.ds+i.sz*d;
sz+=i.sz;
}
info operator-(const info&i)const{
return {ds-i.ds,sz-i.sz};
}
i64 operator*(const info&i){
return ds*i.sz+i.ds*sz;
}
};
struct{
int ed[BN],ed1[BN];
info ds0[BN],ds1[BN];
int b,b1,_ds0,_ds1,_dc;
void init(int p,int d,int _b1){
clr(ds0,bp+2);
clr(ds1,bp+2);
clr(ed1,bs[_b1].sz);
b=p[bid],b1=_b1,_ds0=_ds1=_dc=0;
Block&B=bs[b];
p-=B.idl;
B.bfs(p,d,ed,_ds0,_ds1,_dc);
ds0[b]={_ds0,_dc};
if(B.btm)ds1[b]={_ds1,_dc};
B.qs.push_back({B.dep[0][p],(B.btm?B.dep[1][p]:0),d,cur_q});
if(fa[b]){
int f=fa[b],d1=d-B.dep[0][p];
dfs(f,d1,1);
fore(f,i){
int u=ch[i];
if(u!=b)dfs(u,d1,0);
}
}
if(B.btm){
int d1=d-B.dep[1][p];
fore(b,i){
int u=ch[i];
dfs(u,d1,0);
}
}
}
void upd_ds(){
for(int w=1;w<bp;++w){
int f=fa[w];
ds0[f].add(ds0[w],d01[f]);
}
for(int w=bp;w;--w){
fore(w,i)ds1[w].add(ds0[ch[i]],0);
fore(w,i){
int u=ch[i];
ds1[u].add(ds1[w]-ds0[u],d01[u]);
}
}
}
void dfs(int w,int d,int tp){
if(d<0)return;
Block&B=bs[w];
int d1=min(B.md[tp]-1,d),dc=B.dc[tp][d1];
ds0[w]={B.dsum[tp][0][d1],dc};
if(B.btm)ds1[w]={B.dsum[tp][1][d1],dc};
if(w==b1){
F3(i,1,B.sz)ed1[i]=(B.dep[tp][i]<=d);
for(int i=B.sz-1;i;--i)ed1[B.fa[i]]+=ed1[i];
}
d-=d01[w];
if(tp){
int f=fa[w];
if(!f)return;
dfs(f,d,1);
fore(f,i){
int u=ch[i];
if(u!=w)dfs(u,d,0);
}
}else fore(w,i){
dfs(ch[i],d,0);
}
}
}i0,i1;
void query(int p0,int d0,int p1,int d1){
i0.init(p0,d0,p1[bid]);
i1.init(p1,d1,p0[bid]);
i64 s=0;
int b0=p0[bid],b1=p1[bid];
Block&B0=bs[b0],&B1=bs[b1];
if(b0==b1){
s+=i0.ds0[b0]*i1.ds0[b1]-2*B0.cal(i0.ed,i1.ed);
}else{
s+=i0.ds0[b0]*i1.ds0[b0]-2*B0.cal(i0.ed,i1.ed1);
s+=i0.ds0[b1]*i1.ds0[b1]-2*B1.cal(i1.ed,i0.ed1);
}
i0.upd_ds();
for(int w=1;w<=bp;++w){
fore(w,i){
int u=ch[i];
s+=(i0.ds1[w]-i0.ds0[u])*i1.ds0[u];
s+=i0.ds0[u]*i1.ds1[w];
}
}
ans[cur_q]+=s;
}
int cur_d,qs[N][2],qp[N];
void dfs(int w,int d,int tp){
for(Query &q:bs[w].qs){
int _d=q.d-(tp?q.d1:q.d0)-d;
if(_d>=0)qs[q.id][qp[q.id]++]=_d*2+cur_d;
}
d+=d01[w];
if(tp){
int f=fa[w];
if(!f)return;
dfs(f,d,1);
fore(f,i){
int u=ch[i];
if(u!=w)dfs(u,d,0);
}
}else fore(w,i)dfs(ch[i],d,0);
}
void offline(){
for(int w=1;w<=bp;++w){
clr(qs,m+2);
clr(qp,m+2);
int f=fa[w];
if(f){
cur_d=0;
dfs(f,0,1);
fore(f,i){
int u=ch[i];
if(u!=w)dfs(u,0,0);
}
}
cur_d=1;
fore(w,i)dfs(ch[i],0,0);
Block &b=bs[w];
b.offline(0,0);
if(b.btm){
b.offline(0,1);
b.offline(1,1);
}
}
}
#undef fore
}
void Block::offline(int d0,int d1){
using BlockTree::qs;
using BlockTree::qp;
int mx0=md[d0],mx1=md[d1],*D0=dep[d0],*D1=dep[d1];
static i64 tmp[BN][BN],s[BN];
F(a,mx0){
clr(s,sz);
F3(i,1,sz)s[i]=(D0[i]<=a);
for(int i=sz-1;i;--i)s[fa[i]]+=s[i];
s[0]=0;
F3(i,1,sz)s[i]+=s[fa[i]];
clr(tmp[a],mx1);
F3(i,1,sz)tmp[a][D1[i]]+=s[i];
F3(i,1,sz)tmp[a][i]+=tmp[a][i-1];
}
for(int i=1;i<=m;++i)if(qp[i]==2){
int a=qs[i][0],b=qs[i][1];
if(!(((a^d0)|(b^d1))&1)){
a=min(mx0-1,a>>1);
b=min(mx1-1,b>>1);
ans[i]+=dc[d0][a]*dsum[d1][0][b]+dc[d1][b]*dsum[d0][0][a]-2*tmp[a][b];
}
}
}
int main(){
fread(ib,1,sizeof(ib),stdin)[ib]=0;
n=read();
B=sqrt(n)*1.5;
e[0].push_back(1);
for(int i=2;i<=n;++i){
int f=read();
e[f].push_back(i);
fa[i]=f;
}
BlockTree::build();
m=read();
for(cur_q=1;cur_q<=m;++cur_q){
int p0=read(),d0=read(),p1=read(),d1=read();
BlockTree::query(p0[id],d0,p1[id],d1);
}
BlockTree::offline();
for(int i=1;i<=m;++i)print(ans[i]);
fwrite(ob,1,op-ob,stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2102ms
memory: 43036kb
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:
73808947154124 2800775837495 107391388611701 211146819488585 221669066597727 54124709555700 17436111304599 161413266305868 900759940263 26714622986205 149295340482783 79313462796898 286910889419867 32997264554145 4452115674685 253703644740290 111075178617610 106580063498028 256145288437778 895855839...
result:
ok 100000 lines
Test #2:
score: 0
Accepted
time: 1495ms
memory: 38256kb
input:
85715 1 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 35 46 47 48 49 34 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:
3752398888991 266269519835 882277251558 2007911217844 1661526278229 5240348147069 5676469052468 6347466839157 548943820155 7245636377732 689725283530 439570538380 4666567503610 1515943918901 4699556007208 989261721206 3345480683492 3007541400824 1505234145678 322012918900 3986619661792 1280768969114...
result:
ok 100000 lines
Test #3:
score: 0
Accepted
time: 1436ms
memory: 32424kb
input:
85715 1 1 1 2 3 4 5 6 8 8 10 10 12 13 13 14 15 17 17 19 19 20 21 23 24 25 26 26 27 28 29 30 32 32 34 35 36 36 37 38 40 40 42 42 44 44 46 46 48 48 50 50 52 53 53 55 55 56 58 58 3 60 62 63 63 64 66 66 67 68 69 70 72 73 74 74 75 77 77 78 80 80 82 82 84 85 86 86 87 89 90 91 92 92 94 95 95 96 97 99 100 1...
output:
5356830438224 87009737717 3546122486445 84631188726 1872964753942 3441836105419 3294738961602 1489687022230 167282568978 4086293009346 104028537863 3331145295 599798596398 506291736995 187127453900 4522633873 142450058331 563876098075 5097470005944 534718219693 73029961871 2023006913550 338326881082...
result:
ok 100000 lines
Test #4:
score: 0
Accepted
time: 1289ms
memory: 32644kb
input:
85715 1 1 1 3 3 3 4 4 6 8 7 10 9 11 11 15 16 17 17 18 18 20 19 21 22 22 24 26 27 28 29 30 32 33 32 33 35 34 37 36 40 38 42 42 44 43 45 46 45 49 48 51 49 53 54 54 55 55 58 58 59 61 62 60 64 62 63 67 67 69 69 71 71 72 72 75 76 50 78 76 79 81 81 83 84 53 84 84 88 86 88 91 90 93 93 94 94 96 95 98 99 99 ...
output:
2499989738566 273520567531 67008666999 538975194422 61652825747 1030830398159 6505785154 972668226505 12535928694 2811033700533 4960615048216 1490875027560 2935375271 1869546766650 4293011773423 51575065598 2229239791726 97135074815 561678073387 9022106 3901515618380 5311352972 457804845248 14983976...
result:
ok 100000 lines
Test #5:
score: 0
Accepted
time: 1167ms
memory: 32248kb
input:
85715 1 1 1 1 2 5 4 2 6 7 3 9 10 8 10 12 9 14 13 12 18 21 17 23 22 18 22 21 27 29 29 29 31 33 27 30 30 32 38 37 33 41 35 36 37 41 45 45 43 44 44 45 52 46 51 50 56 51 54 53 56 55 55 60 58 58 59 60 68 63 70 69 66 72 71 71 72 71 78 76 77 76 80 77 79 84 8 83 88 88 89 91 87 88 92 93 90 94 97 98 100 95 97...
output:
677505341317 1162363847 1231462146102 866789581333 2627483744 83009317927 2942521303925 4515880404092 2048449700182 445078713 622147305 840948842475 2294808647148 4867266399457 320505731 15113078776 753519589400 44389540181 33917948838 33240522684 19172977334 223334146913 5344700086315 455674733677 ...
result:
ok 100000 lines
Test #6:
score: 0
Accepted
time: 1636ms
memory: 39360kb
input:
85715 1 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:
6168385054056 20213064547082 205949635500 11158963374 33188214363159 43059699659 955602778272 36099888899496 1545836983444 5490729746040 9678814546112 2411105010812 18935545621432 1688964028151 364690136128 15587073980 35869099780868 3162302468672 36725691384328 24972114011069 19296941530201 4141091...
result:
ok 100000 lines
Test #7:
score: 0
Accepted
time: 1216ms
memory: 32756kb
input:
85715 1 1 1 3 4 4 5 7 8 9 10 10 11 13 14 14 15 17 17 18 19 20 22 23 24 24 26 27 27 28 30 31 32 33 33 35 36 36 37 38 40 41 41 43 44 45 46 46 47 49 50 51 52 53 54 54 55 57 58 59 60 60 62 63 64 64 65 66 68 68 70 70 72 73 74 75 76 77 77 78 79 81 81 82 84 85 85 87 88 88 90 90 92 92 94 94 96 96 98 98 100 ...
output:
20384058350136 9557256414971 1757001949107 15022129193090 13883136178264 2946079657471 19054752417795 380315871959 6022105200602 505727917035 1635669284606 63411724152 4883684439984 463112067709 4282025571053 12475222122205 24118980941377 8002072058513 5689638611200 2202732607603 2561529957202 15923...
result:
ok 100000 lines
Test #8:
score: 0
Accepted
time: 1127ms
memory: 30628kb
input:
85715 1 1 1 1 4 5 6 4 8 6 9 10 10 11 14 13 16 14 15 19 19 19 22 20 22 23 25 24 26 26 29 1 30 33 34 35 34 37 35 36 37 41 42 41 41 45 43 47 47 46 48 48 49 50 51 52 54 54 55 57 60 59 60 62 64 63 64 66 67 67 69 68 71 72 74 75 76 76 77 79 77 80 82 81 81 85 83 85 86 88 88 89 89 93 94 95 96 96 97 99 97 100...
output:
8282168529910 290529824680 978768968748 9936797063336 4712095436332 2644421277420 3164867328356 11258803690370 8189656430646 5027172496995 17317406454028 17142536177596 130083547167 125238500038 1932138692049 104136026163 986465431216 310078898213 2246932846726 17800240436783 19190812588074 31694380...
result:
ok 100000 lines
Test #9:
score: 0
Accepted
time: 1084ms
memory: 34208kb
input:
85715 1 1 1 2 1 5 1 7 8 9 9 7 5 9 12 10 12 14 14 12 18 21 17 19 24 24 19 26 23 29 29 30 29 30 30 28 33 35 32 32 34 39 38 38 41 45 17 47 46 47 44 50 46 53 54 55 51 55 52 54 56 61 58 61 57 60 59 66 63 64 64 65 67 72 67 68 69 70 77 76 73 80 81 76 79 80 84 82 82 87 88 84 91 90 94 90 93 91 94 98 98 95 97...
output:
149733058516 108027705012 462832369794 10580587990107 920138340324 1459829753402 198427538581 6729958859563 391552948445 10715526552 255613032 8409698878559 265976250169 5795469565624 102471104743 10861536092784 1035665660344 1925780583174 449776306500 10501018239351 1824282193512 1760811121225 1043...
result:
ok 100000 lines
Test #10:
score: 0
Accepted
time: 1761ms
memory: 40716kb
input:
85715 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 14 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:
24912780117266 102053219679020 19909780885540 13149776547114 27331548085208 49754208859974 28959997032169 21614083179732 77730019267240 113950520653305 13191051818376 19524746046642 98120248973685 50693801936644 101755489581537 838206239777 21457473687856 79953627111214 15894281421446 5296472613614 ...
result:
ok 100000 lines
Test #11:
score: 0
Accepted
time: 1210ms
memory: 37228kb
input:
85715 1 1 1 2 3 4 5 6 7 8 9 10 11 12 14 15 15 16 17 19 20 20 21 22 23 25 25 26 27 28 30 30 32 32 33 35 35 36 38 38 39 41 42 42 44 45 46 46 48 48 49 50 51 52 53 55 56 56 57 58 59 60 62 62 63 65 65 66 67 68 70 70 71 73 74 75 75 77 77 79 80 80 81 82 83 85 86 86 88 89 90 90 92 93 93 94 95 97 98 98 100 1...
output:
11353546521917 31096709969333 152782996764 13307432926845 31226170001025 10338595126810 3240200690072 50839476263152 36274175323210 8052416014610 631622866501 4782499565921 34159308569298 19583620524979 15510369200753 34288692589692 3218412366636 7043698441202 13176682978205 22360144211742 118717850...
result:
ok 100000 lines
Test #12:
score: 0
Accepted
time: 1242ms
memory: 25740kb
input:
65535 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...
output:
608955376 70293 3260908 50976367 1494252 742943 329809924 547558400 22147675 63892 807859 15713111 6545519 6847609856 90956 9916 676204 3242937 4923239 10465523 12919053 107332 7623828480 3924764672 29329529 155017 490363 54665129 26297361 133940 10158247 2284 16721909 369674883 580299 25839479 5152...
result:
ok 100000 lines
Test #13:
score: 0
Accepted
time: 1202ms
memory: 38652kb
input:
85715 1 1 1 1 3 5 6 7 7 9 8 10 9 11 14 15 16 15 16 19 17 18 20 22 21 23 26 26 26 29 30 28 29 33 32 32 36 34 35 36 39 39 39 42 41 44 43 45 47 49 49 51 51 51 53 54 55 54 58 58 60 61 59 60 61 62 65 67 68 66 70 70 69 71 74 72 76 75 75 76 80 79 81 83 81 83 86 84 87 86 89 90 89 92 92 93 95 95 96 99 98 99 ...
output:
23290485892160 7010017723342 221311200583 53941907963797 15138112014038 14540304654887 855685634393 16307876605091 10117319243511 25896596346124 2210264310611 11095140179867 7254093083190 9172307729492 29037778291730 5295557041877 4036808135155 9371040494502 13299109419503 33906280539724 24931787502...
result:
ok 100000 lines
Test #14:
score: 0
Accepted
time: 1104ms
memory: 32324kb
input:
85715 1 1 1 1 2 4 1 7 5 5 3 11 9 13 8 15 16 16 13 17 15 15 15 20 18 21 24 20 24 25 27 29 30 32 29 32 36 35 37 36 35 37 35 37 37 39 46 42 44 45 47 50 48 47 51 54 52 53 54 53 60 61 58 57 64 58 59 62 61 62 63 64 71 73 69 75 71 71 73 72 73 81 75 78 81 78 86 85 86 84 83 88 86 92 89 92 94 95 95 96 99 101 ...
output:
19617687420288 14027952420606 18341803067659 1440146139314 5191037437372 13610922296620 311272563941 13524913819802 19610979336176 240869243277 8550878337160 19199154662038 12932268616083 4846080832192 26904860104338 13645648776823 28432619693378 21960605705314 15843752811488 2633663698368 686311077...
result:
ok 100000 lines
Test #15:
score: 0
Accepted
time: 1348ms
memory: 34584kb
input:
99827 1 2 3 4 5 6 7 8 9 9 11 12 13 10 14 15 17 18 16 19 20 21 23 22 25 24 27 26 28 30 29 32 32 31 34 35 36 37 38 39 41 4 4 44 4 4 43 4 43 44 48 52 44 43 4 51 53 4 58 60 52 47 56 48 65 53 4 67 46 51 65 49 63 65 60 59 77 78 52 66 62 45 62 44 56 56 49 48 84 75 4 44 60 49 44 54 94 60 52 77 92 81 84 87 5...
output:
18936093102368 8330012551290 31524350784314 21800964361831 6286085734796 53771844253662 15981104062504 42082621150408 30429604052645 65853966626131 18070959693603 15962374542101 21519109743904 2771573827951 24597349975293 87277506548238 22481190195058 85717244216809 49875425768929 42282833159694 455...
result:
ok 100000 lines
Test #16:
score: 0
Accepted
time: 1346ms
memory: 39612kb
input:
99204 1 2 3 4 5 6 7 8 9 10 5 12 11 12 15 14 17 16 16 19 20 22 23 22 13 22 25 22 28 18 26 21 32 30 24 27 29 34 37 33 38 40 31 38 39 43 35 38 36 42 38 38 44 45 53 47 50 56 59 60 55 58 59 54 51 49 62 67 69 59 64 46 72 74 65 71 75 78 70 73 52 79 68 81 77 80 82 85 57 86 83 91 84 61 95 87 94 98 86 96 66 8...
output:
36547118424044 24649117613240 18442532254623 1131093362168 16268203844842 5962597994890 2709079678012 1851209592952 6576435970058 25925900039856 32828081387617 1233502933313 175669816324 4900810774618 36114261694660 2352238547873 57296196267421 4742712000808 20287267545330 47987490643445 38524556077...
result:
ok 100000 lines
Test #17:
score: 0
Accepted
time: 1400ms
memory: 35548kb
input:
98368 1 2 3 4 1 1 1 5 9 6 7 11 8 10 15 13 14 17 18 19 20 16 22 12 23 24 25 28 26 21 27 29 30 34 35 31 27 32 36 38 41 42 41 44 37 40 43 45 45 33 51 50 46 53 50 52 50 57 49 39 59 62 48 64 58 47 63 65 67 68 70 60 66 71 66 73 74 76 76 72 75 76 55 76 78 61 79 82 86 87 54 84 91 77 85 81 69 76 80 99 76 101...
output:
48322078018547 21236528664853 24072317291854 18709182635808 4682129900952 6917473901696 14008712802354 17688962774750 5375881448956 24615692670399 12141481836428 6527051651046 16750691097560 40959277122654 19242300050368 6531914049104 14011201117712 7971600371866 10555166612760 32035940152469 696767...
result:
ok 100000 lines
Test #18:
score: 0
Accepted
time: 967ms
memory: 26776kb
input:
100000 1 2 3 4 5 6 7 8 9 4 6 8 6 5 5 9 3 10 7 2 1 4 8 6 10 8 3 7 1 2 9 3 7 4 10 6 2 2 6 6 1 7 5 3 2 9 4 3 4 1 9 5 10 7 6 6 5 7 4 1 4 6 7 1 10 10 7 4 8 1 8 8 8 9 2 3 7 7 6 1 4 5 1 8 3 10 1 3 4 8 2 8 4 8 1 2 3 2 4 7 8 6 8 7 5 2 2 1 8 8 3 6 9 7 5 1 10 3 5 3 9 9 4 1 2 7 9 6 5 3 10 1 8 6 5 4 9 6 9 3 9 2 ...
output:
40808334015 4514043596 36439806262 160076 9799450642 10670317934 26467188642 30117230941 569601 2024373718 14305992483 209742 340112 2105894033 29184419939 4477460920 40808334015 380314 6211639014 22019478953 46476523128 349667 2594248334 46476523128 20565191267 9811307050 3 1200424 3790480358 51080...
result:
ok 100000 lines
Test #19:
score: 0
Accepted
time: 1251ms
memory: 31412kb
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:
2013831764637 886472700494 150287747447 2355730610580 54594525526 400610252215 2375824970432 2931430938770 1072592069264 596994711196 395117862314 239125704918 605605375116 494940472379 362008300491 1392556293331 39067278298 206294856778 575073021347 952296799407 1038317655995 310207886142 191951647...
result:
ok 100000 lines
Test #20:
score: 0
Accepted
time: 1422ms
memory: 37700kb
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:
91453525122668 39232836433897 97766246643326 7376429207177 37312940103697 105801147649766 6568528986570 75884771486018 4681874572834 3775612742801 17118000043059 50637295154322 11435005461080 79246986782907 111390064244747 20602376787150 81922366908282 25927393330106 12938210371888 42957915865238 52...
result:
ok 100000 lines
Test #21:
score: 0
Accepted
time: 1704ms
memory: 40720kb
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:
20812203759388 147615817305858 83097235508 195662292880048 71469063630044 43010526548019 20773750643136 107397849506101 122670006405226 16804700858116 9772887341766 71516868224011 139736844422996 35283133440804 79669874345129 31568585237 6237258085769 31022901109255 41908972320465 45480912909105 496...
result:
ok 100000 lines
Test #22:
score: 0
Accepted
time: 1888ms
memory: 43304kb
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:
87447081280008 134340152351709 193567719052678 54838440260568 41221747010098 15632371133105 12038132079034 150102899559284 36546425242302 121008116169730 146637077932740 24690724702176 279856558609457 18490930830648 208876498901481 146179234967159 116457413805634 171782151266920 19907726398478 10757...
result:
ok 100000 lines
Test #23:
score: 0
Accepted
time: 1490ms
memory: 33128kb
input:
100000 1 2 1 1 2 4 5 3 9 5 3 4 3 2 12 16 6 3 2 1 16 9 4 6 19 12 3 22 11 7 22 3 19 34 8 22 20 13 7 20 9 32 6 43 16 6 37 12 1 15 39 44 7 27 30 47 11 50 44 60 48 3 47 7 30 22 30 36 33 47 57 35 15 32 30 25 36 56 14 80 15 18 8 43 44 62 8 61 25 42 44 2 65 56 27 41 70 29 17 32 27 91 58 67 93 59 67 18 35 38...
output:
23562 1567066768 157230992815 198112596570 158967604 783 29450472 197275577542 323934 28129418522 1876663885 672821267 9808 8655983 41454184 190088156510 14438923 197351760793 41766 29342772 6227498 56731993614 184201024866 198093876912 174653782 3250289 182991 196487726484 8192132 12099773 89720506...
result:
ok 100000 lines
Test #24:
score: 0
Accepted
time: 2080ms
memory: 46484kb
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:
28715087501087 10702999984503 268483578028548 25161940976900 107104547652524 90175289474703 30605492616838 135053295109727 224803951289570 42728597308774 8503053936911 144282894472824 52784254624602 42497413475475 19012287532318 156270808700238 294821685071264 70498989911607 18247070735263 154145328...
result:
ok 100000 lines
Test #25:
score: 0
Accepted
time: 1721ms
memory: 37112kb
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:
603396644921 432936112522 54979248053 702892120 4666932763341 5710715338 11213978314 4672562596 11937355898 2471085421277 568206029886 4432916832228 943711985810 4005785297 13537466679 23968157500 6888422424 4731888292230 3781431896481 6971177085 579792755264 984676504706 1967083206057 2065799769154...
result:
ok 100000 lines
Test #26:
score: 0
Accepted
time: 1750ms
memory: 36584kb
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:
88630980007 5366068531391 410742370921 5745187793402 6324752486125 636916528645 5681865916216 4168150132454 5290296267691 373139414338 1064392765650 23108709635 25502636615 3929624758518 3311552576481 6202498472765 1005949713794 99337178924 3101588059052 5404948285187 4070575102998 6072420354087 543...
result:
ok 100000 lines
Test #27:
score: 0
Accepted
time: 1415ms
memory: 36364kb
input:
85715 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 11 25 26 27 28 29 30 31 32 33 34 35 36 37 38 29 40 41 32 43 44 45 46 28 48 40 50 51 52 53 54 55 56 57 29 59 60 61 62 63 64 65 23 67 68 69 67 71 72 73 74 75 76 77 78 79 59 81 82 83 84 85 86 87 88 89 90 91 92 93 27 95 96 97 98 99 100 ...
output:
1080016798929 1022502087303 430651987453 3106311954 1074010232132 1048069936037 267001065960 215996996116 18020458548 34657197 274505152028 670256076424 65216347841 21617175511 994492150960 30805311678 1530435934 178519475 840124051 68261835680 1060954387868 7651017 945219042 11938738534 17670635306...
result:
ok 100000 lines
Test #28:
score: 0
Accepted
time: 1488ms
memory: 34248kb
input:
85715 1 2 2 3 4 5 6 6 7 8 9 11 7 12 13 15 15 16 18 18 20 20 22 22 24 24 26 26 28 28 29 30 32 15 34 36 18 37 37 39 39 41 41 43 43 44 46 46 25 48 28 51 52 52 54 55 56 57 57 59 59 60 62 62 63 65 66 66 68 69 69 71 71 42 46 74 76 77 77 78 80 81 82 82 83 47 85 87 88 89 90 91 92 93 94 94 95 97 66 98 83 101...
output:
336660910154 80340941 250785891 16177004 16514019869 165503703730 32391598932 755856376449 949990718923 388268950488 66703626538 40224 50354556629 752770341925 21249186379 627795887928 704092025 396897302748 718235335489 296041658706 4228283023 2434255126 176852521300 1543487486 23745753156 16814803...
result:
ok 100000 lines
Test #29:
score: 0
Accepted
time: 1399ms
memory: 32564kb
input:
85715 1 1 2 2 1 4 3 6 5 7 8 4 9 12 14 14 8 16 15 16 14 20 21 22 24 22 23 26 25 29 28 31 30 30 34 32 5 37 38 37 40 39 42 43 43 45 46 44 48 48 48 8 51 52 54 52 56 56 55 57 60 59 28 62 62 65 66 67 66 67 67 8 69 72 72 73 76 76 46 76 77 79 71 82 81 83 86 87 86 88 90 88 91 90 1 93 95 96 95 30 98 100 99 10...
output:
3812509961 896303122904 211918 1117701427 159481396537 3209958041 19409527741 31720422144 43105583604 6259180234 109074368571 43905119 267633932757 14266080792 191631080 7596839983 56519338150 77903126516 14655428 620496327861 1576562974 2632009328 441907783954 42641339941 20926802277 265593207836 4...
result:
ok 100000 lines
Test #30:
score: 0
Accepted
time: 1507ms
memory: 35500kb
input:
85715 1 1 1 3 1 1 6 4 4 2 10 6 12 10 8 8 13 11 13 18 20 14 20 20 17 25 26 20 7 22 28 29 26 32 32 34 34 31 34 32 33 40 41 39 37 11 43 40 44 48 50 51 48 46 48 52 55 57 51 52 58 54 60 58 58 59 63 64 68 62 65 66 65 71 73 69 74 72 75 74 74 76 79 83 78 78 84 80 82 21 83 85 86 89 88 23 89 90 97 99 95 98 43...
output:
34588448524 232763282 126898943299 592547237950 383529812 174023308545 7018405849 9256019 978595742786 950166802918 8045150781 366184687073 476023571 247384688104 410186438437 767953904233 2260061606 315007545 152695546420 403371736260 70565490682 983827270 44161358 3921618896 1715379962 65286886 96...
result:
ok 100000 lines