QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#405654#8630. 字符树dingdingtang11514#10 24ms124588kbC++146.7kb2024-05-06 11:41:002024-05-06 11:41:00

Judging History

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

  • [2024-05-06 11:41:00]
  • 评测
  • 测评结果:10
  • 用时:24ms
  • 内存:124588kb
  • [2024-05-06 11:41:00]
  • 提交

answer

#include <iostream>
#include <cstring> 
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
// #include <bits/stdc++.h>

// #define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define Grf(it,u,to) for(int it=he[u],to;(to=e[it],it);it=nxt[it]) 
#define In __inline 
#define OP operator
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace Mine {
	// mt19937_64 wql(514);
	In int read() {
		ll x=1,a=0;
		char ch=getchar();
		while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
		while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
		return a*x;
	} const int N=5e5+100;
	char ch[N];int n,m,X,fa[N],f[N][21],dep[N];
	
	
	bool No1=1;
	
	In int lca(int x,int y) {
		if(dep[x]<dep[y]) swap(x,y);
		Rof(i,20,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return x;
		Rof(i,20,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
		return f[x][0];
	} int he[N],nxt[N],cf[N],idx=1,e[N];
	void adde(int a,int b,int c) {
		e[++idx]=b,cf[idx]=c,nxt[idx]=he[a];he[a]=idx;
	}
	namespace sol {
		namespace Mine {
			// mt19937_64 wql(514);
			In ll read() {
				ll x=1,a=0;
				char ch=getchar();
				while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
				while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
				return a*x;
			} const int N=1e6+100;
			struct ACAM {
				int son[N][26],fail[N],idx=0,tr[N],dfn[N],ed[N],tot;
				vector<int> fs[N];
				void dfs(int u) {
					dfn[u]=++tot; for(int to:fs[u]) {dfs(to);} ed[u]=tot;
				} void build() {
					queue<int> q; For(i,0,25) if(son[0][i]) q.push(son[0][i]);
					while(q.size()) { int u=q.front();q.pop();
						// printf("%d\n",u);
						For(i,0,25) {
							if(!son[u][i]) son[u][i]=son[fail[u]][i];
							else fail[son[u][i]]=son[fail[u]][i],q.push(son[u][i]);
						}
					} For(i,1,idx) fs[fail[i]].push_back(i);
					// For(i,0,idx) {for(int j:{'w'-'a','x'-'a'}) printf("%d ",son[i][j]);puts("");}puts("");
					dfs(0); //For(i,0,idx) printf("%d ",dfn[i]);
					// puts("");For(i,0,idx) printf("%d ",fail[i]);puts("");
				} void mdf(int pos,int val) {for(;pos<=tot;pos+=pos&-pos) tr[pos]+=val;}
				In int qry(int pos) {int ret=0; for(;pos;pos-=pos&-pos){ret+=tr[pos];}return ret;}
				In int get(int u) {return qry(ed[u])-qry(dfn[u]-1);}
			} A1,A2;int he[N],nxt[N<<1],e[N<<1],n,m; char w[N<<1];
			namespace E {int idx=1; void adde(int a,int b,char d) {e[++idx]=b,w[idx]=d,nxt[idx]=he[a],he[a]=idx;}}
			using E::adde; struct node { int qid,val; } ; vector<node> b1[N],b2[N];
			int fa[N][23],dep[N];char from[N]; void get_fa(int u,int f) {
				dep[u]=dep[f]+1;fa[u][0]=f; For(i,1,22) fa[u][i]=fa[fa[u][i-1]][i-1];
				Grf(it,u,to) {if(to!=f) {from[to]=w[it];get_fa(to,u);}}
			} In int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y);
				Rof(i,22,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
				if(x==y) return x;
				Rof(i,22,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
				return fa[x][0];
			} struct Que {int x,y,top,a,b,ans;} q[N];
			char S[N];int ls; In int FA(int u,int x) {Rof(i,19,0) {if(x>=(1<<i))x-=(1<<i),u=fa[u][i];}return u;}
			char ch[N],lch; In int kmp() {
				static int nxt[N];
				// printf("%s ",ch+1,S);
				nxt[1]=0; int j=0; For(i,2,ls) {
					while(j && S[j+1]!=S[i]) j=nxt[j];
					if(S[j+1]==S[i]) j++;
					nxt[i]=j;
				} int ret=0; j=0; For(i,1,lch) {
					while(j && S[j+1]!=ch[i]) j=nxt[j];
					if(S[j+1]==ch[i]) j++;
					if(j==ls) ret++,j=nxt[j];
				} return ret;
			} void dfs(int u,int ff,int r1,int r2) {
				A1.mdf(A1.dfn[r1],1);A2.mdf(A2.dfn[r2],1);
				for(auto &j:b1[u]) q[j.qid].ans+=j.val*A1.get(q[j.qid].a);
				for(auto &j:b2[u]) q[j.qid].ans+=j.val*A2.get(q[j.qid].b);
				Grf(it,u,to) if(to!=ff) dfs(to,u,A1.son[r1][w[it]-'a'],A2.son[r2][w[it]-'a']);
				A1.mdf(A1.dfn[r1],-1);A2.mdf(A2.dfn[r2],-1);
			} signed main() {
				get_fa(1,0);
				For(i,1,m) {
					int opt=read(); if(opt==1) No1=0;
					
					q[i].x=read();q[i].y=read();q[i].top=lca(q[i].x,q[i].y);
					// printf("%d %d %d\n",q[i].x,q[i].y,q[i].top);
					 scanf("%s",S+1);ls=strlen(S+1);int u=0; For(i,1,ls) {
						int &to=A1.son[u][S[i]-'a']; if(!to) to=++A1.idx;
						u=to;
					}q[i].a=u; u=0; Rof(i,ls,1) {
						int &to=A2.son[u][S[i]-'a']; if(!to) to=++A2.idx;
						u=to;
					}q[i].b=u; if(q[i].x!=q[i].top && q[i].y!=q[i].top) {
						int b=min(ls-1,dep[q[i].x]-dep[q[i].top]);lch=b;
						for(int a=1,j=FA(q[i].x,dep[q[i].x]-dep[q[i].top]-b);j!=q[i].top;j=fa[j][0],a++) ch[a]=from[j];
						b=min(ls-1,dep[q[i].y]-dep[q[i].top]);lch+=b;
						for(int a=lch,j=FA(q[i].y,dep[q[i].y]-dep[q[i].top]-b);j!=q[i].top;j=fa[j][0],a--) ch[a]=from[j];
						q[i].ans=kmp();
					}
					if(dep[q[i].x]-dep[q[i].top]>=ls) 
						b2[q[i].x].push_back((node){i,1}),b2[FA(q[i].x,dep[q[i].x]-dep[q[i].top]-ls+1)].push_back((node){i,-1});
					if(dep[q[i].y]-dep[q[i].top]>=ls)
						b1[q[i].y].push_back((node){i,1}),b1[FA(q[i].y,dep[q[i].y]-dep[q[i].top]-ls+1)].push_back((node){i,-1});
				} A1.build(),A2.build(); dfs(1,0,0,0);
				For(i,1,m) printf("%d\n",q[i].ans);
				return 0;
			}
		} using namespace Mine;
	}
	char rd[N];
	namespace S0 {
		int ch[N],lch,S[N],ls;
		
		In int kmp() {
			static int nxt[N];
			nxt[1]=0; int j=0; For(i,2,ls) {
				while(j && S[j+1]!=S[i]) j=nxt[j];
				if(S[j+1]==S[i]) j++;
				nxt[i]=j;
			} int ret=0; j=0; For(i,1,lch) {
				while(j && S[j+1]!=ch[i]) j=nxt[j];
				if(S[j+1]==ch[i]) j++;
				if(j==ls) ret++,j=nxt[j];
			} return ret;
		}
		void solve0() {
			while(m--) {
				int opt=read(),x=read(),y=read();scanf("%s",rd+1);
				For(i,1,X) S[i]=rd[i]-'0';
				int p=lca(x,y);//printf("P: %d\n",dep[p]);
				if(opt==1) {int pos=1;
					while(x!=p) cf[x]=S[pos++],x=fa[x];
					pos=X;
					while(y!=p) cf[y]=S[pos--],y=fa[y];
				} else { lch=0;ls=X;
					while(x!=p) ch[++lch]=cf[x],x=fa[x];
					int pos=lch+dep[y]-dep[p];lch+=dep[y]-dep[p];
					// printf("POS %d\n",pos);
					while(y!=p) ch[pos--]=cf[y],y=fa[y];
					// For(i,1,lch) printf("%d ",ch[i]);
					// puts("");
					printf("%d\n",kmp());
				}
			}
		}
	} 
	signed main() {
		n=read(),m=read(),X=read();
		For(i,2,n) f[i][0]=fa[i]=read();
		For(i,1,n) {dep[i]=dep[fa[i]]+1;For(j,1,20) f[i][j]=f[f[i][j-1]][j-1];}
		scanf("%s",rd+1);
		For(i,2,n) {adde(fa[i],i,rd[i-1]-'0');}
		if(n<=250 && m<=250) S0::solve0();
		else {
			
			For(i,2,n) sol::adde(i,fa[i],cf[i]+'0'),sol::adde(fa[i],i,cf[i]+'0');
			sol::n=n,sol::m=m;
			sol::main();
		}
		return 0;
	}
}signed main() {
	// freopen("homework.in","r",stdin);
	// freopen("homework.out","w",stdout);
	return Mine::main();
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 16ms
memory: 124588kb

input:

250 250 62
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 30 67 68 8 70 16 72 3 74 75 32 77 75 31 80 81 65 83 30 19 49 4 1 89 57 91 92 43 94 95 96 85 51 32 100 8...

output:

1
1
1
1
1
1
1
1
0
1
1
1
1
0
0
1
1
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
2
3
0
0
0
4
4
0
0
0
0
0
2
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
1
0
0
10
0
0
0
0
0
0
2
0
0
0
0
0
0
0
3
0
2
0
1
0
0
7

result:

ok 118 numbers

Test #2:

score: 10
Accepted
time: 11ms
memory: 118440kb

input:

250 250 6
1 1 1 4 1 1 1 1 1 1 1 1 1 14 1 1 1 1 19 1 1 1 1 24 1 26 27 28 1 30 1 32 1 1 35 1 37 1 1 1 1 1 43 44 45 1 47 1 1 1 1 1 53 54 1 56 57 58 1 60 1 62 63 64 65 1 1 68 69 70 71 1 1 1 1 76 77 78 79 1 81 1 83 84 1 1 1 88 89 1 91 1 93 94 1 96 97 98 99 1 1 102 103 1 105 106 107 108 1 110 111 112 113 ...

output:

1
1
1
0
0
0
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
0
1
1
0
1
0
0
1
0
0
0
3
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
0
0
3
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
2
2
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
1
0
1

result:

ok 118 numbers

Test #3:

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

input:

250 250 6
1 2 2 4 5 2 7 2 8 10 11 12 13 14 14 16 17 16 19 20 21 22 1 24 16 26 27 28 29 23 31 20 33 34 35 15 37 38 39 40 41 42 30 44 45 46 47 32 49 50 34 52 53 54 7 56 9 58 59 60 52 42 63 64 65 43 67 68 69 70 71 72 11 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 20 66 95 96 97 9 99 100 10...

output:

0
1
1
1
2
1
0
0
8
1
1
0
0
1
1
2
3
1
1
1
1
3
1
0
1
2
0
2
0
8
1
0
2
1
0
2
1
1
3
0
0
1
0
1
0
1
0
0
1
0
2
0
0
3
0
0
0
3
2
0
3
0
5
0
13
5
0
0
7
4
1
0
0
0
1
0
3
0
0
7
0
0
6
0
9
3
8
0
3
7
7
0
15
1
0
8
0
1
6
10
10
0
2
1
0
0
0
3
0
2
6
3
0
3
0
0
2
7
2
0
2
6
17
2
0
0
0
0
0

result:

ok 129 numbers

Test #4:

score: 10
Accepted
time: 12ms
memory: 124580kb

input:

246 250 113
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 ...

output:

1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
6
1
0
1
0
2
0
2
1
1
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
1
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 128 numbers

Test #5:

score: 10
Accepted
time: 15ms
memory: 122548kb

input:

249 250 47
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 1 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 1 1 70 71 1 73 74 75 76 1 78 1 80 1 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 1 99 1 101 1 1...

output:

1
1
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
1
1
1
0
0
1
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 118 numbers

Test #6:

score: 10
Accepted
time: 24ms
memory: 120760kb

input:

250 250 95
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 14 5 98 99 5 ...

output:

1
1
1
1
0
1
1
0
0
1
0
0
0
1
1
0
0
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0

result:

ok 121 numbers

Test #7:

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

input:

250 245 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 26 27 28 29 1 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 1 49 50 51 52 53 1 55 56 57 1 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 1 80 81 82 83 84 85 86 87 88 89 1 91 92 93 94 95 96 97 98 1 100 101 1...

output:

1
0
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
4
0
4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
9
0
0
1
0
0
1
4
0
0
4
0
1
0
0
0
0
2
1
9
0
0
0
7
0
0
2
0
0
0
0
0
0
4
11
0
0
0
0
11
19
1
2
0
0
0
0
0
4
0
0

result:

ok 123 numbers

Test #8:

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

input:

250 250 82
1 1 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 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 10...

output:

1
1
1
1
0
1
1
0
1
1
1
1
0
1
1
1
1
1
0
1
1
1
0
0
1
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
49
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
22
0
0
0
0
0
0
0
0
0
0
0
0
36
0
0
18
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1

result:

ok 118 numbers

Test #9:

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

input:

250 250 7
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 33 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 26 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

1
1
0
0
1
0
1
1
1
1
0
1
1
1
1
0
0
1
1
1
0
0
1
1
0
0
0
0
1
0
1
1
1
1
1
0
1
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
3
0
0
0
0
3
0
8
0
6
0
7
0
10
10
10
0
0
0
0
2
0
2
0
0
0
1
0
9
0
2
17
4
1
0
0
0
0
1
0
0
0
2
0
0
1
4
3
0
0
0
0

result:

ok 123 numbers

Test #10:

score: 10
Accepted
time: 12ms
memory: 120524kb

input:

249 246 2
1 2 2 2 5 4 7 1 2 2 11 3 2 3 15 11 7 13 9 20 6 6 13 8 13 26 27 6 5 30 31 32 33 34 35 2 29 38 39 40 21 30 37 44 45 14 25 32 49 50 51 52 15 5 14 37 23 27 59 60 61 51 63 47 12 34 57 34 69 70 49 60 25 3 75 72 51 78 78 80 81 78 83 84 85 86 62 88 89 90 2 92 93 94 95 96 97 41 89 81 87 102 45 14 3...

output:

2
3
0
1
2
9
1
1
2
2
2
3
2
3
0
0
1
1
1
0
2
1
2
1
2
8
0
1
2
0
0
3
0
2
2
0
0
2
3
0
1
6
0
1
3
4
2
2
5
5
0
0
1
1
3
0
1
5
0
3
0
4
6
4
7
6
0
8
1
4
0
0
3
0
0
0
0
3
0
0
7
0
6
4
1
1
2
1
1
1
4
1
0
1
3
1
1
0
1
0
4
0
1
0
0
0
7
6
0
0
0
2
0
1
1
4
1
0
4
9
1
0
4
2
2

result:

ok 125 numbers

Subtask #2:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

input:

500000 650 769
1 2 3 4 5 6 7 8 9 10 11 12 7 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #21:

score: 0
Runtime Error

input:

500000 499998 1
1 2 3 4 5 6 7 8 1 1 11 12 13 14 15 16 1 1 19 20 21 22 23 24 1 26 1 28 29 30 1 32 33 34 35 1 37 38 39 40 41 42 43 1 45 46 47 48 49 50 1 52 53 54 55 56 57 1 1 60 61 62 63 64 65 66 67 68 69 1 71 1 73 1 75 76 77 78 79 80 81 82 83 1 1 86 87 88 89 1 91 92 93 94 95 96 97 98 99 100 101 102 1...

output:

1
0
0
0
0
0
2
0
1
5
0
1
0
2
4
0
0
1
0
1
0
0
1
0
0
4
3
0
3
1
1
0
3
0
3
1
0
0
1
0
2
0
1
1
1
0
1
1
0
0
0
0
2
0
0
1
1
0
1
1
1
1
1
1
1
1
0
1
1
1
2
3
2
0
1
0
0
0
0
2
4
0
1
0
0
0
3
0
1
1
3
4
0
1
0
0
0
1
0
0
0
0
0
0
0
0
3
0
0
1
1
0
0
0
3
0
0
1
1
1
0
3
6
3
2
0
0
3
0
1
1
1
1
6
1
0
0
3
1
0
1
1
0
3
0
0
3
1
3
0
...

result:


Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Runtime Error

Test #41:

score: 0
Runtime Error

input:

499997 9 40060
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 ...

output:


result:


Subtask #6:

score: 0
Runtime Error

Test #51:

score: 0
Runtime Error

input:

500000 62500 8
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 ...

output:

0
0
122
0
0
489
0
134
0
0
0
0
0
0
0
0
0
28
516
0
0
0
38
0
71
0
0
0
0
0
81
0
0
149
0
0
9
0
536
0
346
0
1137
40
34
0
30
0
4
0
0
413
0
286
0
0
0
1235
0
0
104
300
0
532
0
0
0
0
123
27
0
0
0
51
442
0
66
75
68
544
0
56
33
194
0
0
0
0
0
224
0
7
0
63
9
362
407
0
5
33
0
0
27
10
0
133
174
0
0
0
0
0
1
16
51
11...

result:


Subtask #7:

score: 0
Runtime Error

Test #61:

score: 0
Runtime Error

input:

500000 100000 5
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...

output:

2
5995
10021
58263
12720
1
70338
0
0
35483
0
30541
0
0
4346
31843
50389
21896
0
22132
1
52130
0
0
1
0
0
0
9410
0
58705
90779
1
29762
47315
74100
0
0
5730
6071
1
3931
60337
28004
0
1
0
1
17419
1996
3
0
41417
1
31204
0
12712
0
51145
0
1
0
1
9415
88632
0
1
16474
0
0
1
48315
38729
2159
13207
0
16015
1
8...

result:


Subtask #8:

score: 0
Runtime Error

Test #71:

score: 0
Runtime Error

input:

25000 2500 10
1 2 3 4 5 6 7 8 9 10 1 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...

output:

0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
3
0
0
0
1
0
0
1
0
0
7
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
8
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
4
0
1
0
0
0
0
0
...

result:


Subtask #9:

score: 0
Skipped

Dependency #8:

0%

Subtask #10:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%