QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#374886#2814. 不用找的树Ecec243AC ✓2102ms46484kbC++238.0kb2024-04-02 19:11:542024-04-02 19:11:55

Judging History

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

  • [2024-04-02 19:11:55]
  • 评测
  • 测评结果:AC
  • 用时:2102ms
  • 内存:46484kb
  • [2024-04-02 19:11:54]
  • 提交

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