QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561665#8222. 投票游戏Idtwtei20 752ms72708kbC++205.2kb2024-09-13 07:26:122024-09-13 07:26:12

Judging History

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

  • [2024-09-13 07:26:12]
  • 评测
  • 测评结果:20
  • 用时:752ms
  • 内存:72708kb
  • [2024-09-13 07:26:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
#define pb push_back
const int N=2e5+100;
const ll INF=1e18;
mt19937 rnd(time(0)); 
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,a[N],b[N],fa[N]; ll val[N],ans[N];
int dfn[N],d_c=0,fdfn[N],dep[N],top[N],btm[N],son[N],siz[N];
vector<int> G[N];

struct SEG{
	ll div,v0,v1;
	void print(){ printf("%lld %lld %lld\n", div, v0, v1); }
	ll get(int x){ return x<div?v0:v1; }
	SEG operator+(const SEG &x){ SEG res=x; res.v0=get(x.v0),res.v1=get(x.v1); return res; }
}f[N];

struct TREAP{
	#define lc t[id].ls 
	#define rc t[id].rs
	struct TREE{ int ls,rs,rid; ll v; int b; ll mn,sum; }t[N<<4];
	int rt[N],tot=0;
	
	int make(ll v,int b){ return t[++tot]={0,0,rnd(),v,b,v,b},tot; }
	void pushup(int id){ t[id].sum=t[lc].sum+t[id].b+t[rc].sum,t[id].mn=min({t[lc].mn,t[lc].sum+t[id].v,t[lc].sum+t[id].b+t[rc].mn}); }
	
	int mer(int x,int y){
		if(!x||!y) return x^y;
		if(t[x].rid<t[y].rid) return t[x].rs=mer(t[x].rs,y),pushup(x),x;
		else return t[y].ls=mer(x,t[y].ls),pushup(y),y;
	}
	void spl(int id,int &x,int &y,ll v){
		if(!id) return x=y=0,void();
		if(t[id].v>=v) x=id,spl(rc,rc,y,v),pushup(x);
		else y=id,spl(lc,x,lc,v),pushup(y);
	}
	void ins(int &id,ll v,int b){ int x,y; spl(id,x,y,v),id=mer(x,mer(make(v,b),y)); }
	void del(int &id,int b){ int x,y,z; spl(id,x,z,b),spl(x,x,y,b+1),id=mer(x,z); }
	ll bry(int id,ll v){
		
//		if(v==4){
//			cout<<t[lc].mn<<" "<<t[lc].sum+t[id].v<<" "<<id<<" "<<v<<"\n";
//		}
		
		if(!id) return v;
		if(t[lc].mn<v) return bry(lc,v);
		else if(t[lc].sum+t[id].v<v) return v-t[lc].sum;
		else return bry(rc,v-t[lc].sum-t[id].b);
	}
	void dfs(int id){
		if(lc) dfs(lc);
		printf("%d %d %d %d %d %d %d\n",id, t[id].ls, t[id].rs, t[id].v, t[id].b, t[id].sum, t[id].mn);
		if(rc) dfs(rc);
	}
	#undef lc
	#undef rc
}T;
struct SMT{
	#define lc (id<<1)
	#define rc (id<<1|1)
	#define mid (l+r>>1)
	SEG t[N<<2];
	void pushup(int id){ t[id]=t[lc]+t[rc]; }
	void chg(int id,int l,int r,int ql){
		if(l==r) return t[id]=f[fdfn[l]],void();
		ql<=mid?chg(lc,l,mid,ql):chg(rc,mid+1,r,ql); pushup(id);
	}
	SEG ask(int id,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr) return t[id];
		if(qr<=mid) return ask(lc,l,mid,ql,qr);
		else if(ql>=mid+1) return ask(rc,mid+1,r,ql,qr);
		else return ask(lc,l,mid,ql,qr)+ask(rc,mid+1,r,ql,qr); 
	}
	#undef lc
	#undef rc
	#undef mid
}S;
inline ll get(int x){ return S.ask(1,1,n,dfn[x],dfn[btm[top[x]]]).get(0); }

void dfs0(int u,int fu){
	siz[u]=1,son[u]=0,dep[u]=dep[fu]+1;
	for(int v:G[u]){
		if(v==fu) continue;
		dfs0(v,u),siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v; 
	}
}
void dfs1(int u,int fu,int tp){
	fdfn[dfn[u]=++d_c]=u,btm[top[u]=tp]=u;
	if(son[u]) dfs1(son[u],u,tp);
	for(int v:G[u]) if(v!=fu&&v!=son[u]) dfs1(v,u,v);
}
void dfs2(int u,int fu){
	if(son[u]) dfs2(son[u],u),val[u]+=b[son[u]];
	for(int v:G[u]){
		if(v==fu||v==son[u]) continue;
		dfs2(v,u),val[u]+=b[v];
//		if(u==1) cout<<
		T.ins(T.rt[u],get(v),b[v]);
	}
	f[u].div=f[u].v0=T.bry(T.rt[u],val[u]);
	f[u].v1=T.bry(T.rt[u],val[u]-b[son[u]]);
	
//	cout<<"???"<<u<<" "; f[u].print();
	
	S.chg(1,1,n,dfn[u]);
}

void chg(int x){
	for(;;x=fa[x]){
		ll yf=ans[top[x]];
		S.chg(1,1,n,dfn[x]);
//		cout<<"??"<<x<<" "<<top[x]<<" "<<fa[top[x]]<<"\n";
		x=top[x]; if(fa[x]==0) break;
//		if(fa[x]==1){
//			T.dfs(T.rt[fa[x]]);
//			cout<<yf<<"\n\n";
//		}
		T.del(T.rt[fa[x]],yf);
		
//		if(fa[x]==1) T.dfs(T.rt[fa[x]]);
//		cout<<"??";
		T.ins(T.rt[fa[x]],get(x),b[x]);
		
		//if(fa[x]==1) T.dfs(T.rt[fa[x]]);
		//if(fa[x]==1) cout<<get(x)<<"\n";
		ans[top[fa[x]]]=get(top[fa[x]]);
		f[fa[x]].div=f[fa[x]].v0=T.bry(T.rt[fa[x]],val[fa[x]]);
		f[fa[x]].v1=T.bry(T.rt[fa[x]],val[fa[x]]-b[son[fa[x]]]);
	}
}

signed main(){
	
//	cout<<sizeof(T.t)/1024/1024<<"\n";
	
	T.t[0].mn=INF;
	
	n=rd,m=rd;
	for(int i=2;i<=n;++i) G[fa[i]=rd].pb(i);
	for(int i=1;i<=n;++i) val[i]=a[i]=rd;
	for(int i=1;i<=n;++i) b[i]=rd;
	
	dfs0(1,0),dfs1(1,0,1),dfs2(1,0);
	
//	for(int i=1;i<=n;++i) cout<<son[i]<<" "; puts("");	
//	for(int i=1;i<=n;++i) ans[i]=get(i); 
//	for(int i=1;i<=n;++i) cout<<get(i)<<" "; puts("");
	
	for(int i=1,op,p,x,y;i<=m;++i){
		op=rd; if(op==1) p=rd,x=rd,y=rd; else x=rd,y=rd;
		if(op==1){
			ans[top[p]]=get(top[p]);// cout<<ans[p]<<"\n";
			val[p]+=x-a[p]; a[p]=x;
			f[p].div=f[p].v0=T.bry(T.rt[p],val[p]);
			f[p].v1=T.bry(T.rt[p],val[p]-b[son[p]]);
			chg(p);
			if(fa[p]){
				ans[top[fa[p]]]=get(top[fa[p]]);
				val[fa[p]]+=y-b[p];// cout<<val[fa[p]]<<"\n";
				b[p]=y;
			//	if(p==)
			//	T.dfs(T.rt[fa[p]]); cout<<"\n\n";
				
				if(son[fa[p]]!=p) T.del(T.rt[fa[p]],get(p)),T.ins(T.rt[fa[p]],get(p),b[p]);
				f[fa[p]].div=f[fa[p]].v0=T.bry(T.rt[fa[p]],val[fa[p]]);
				f[fa[p]].v1=T.bry(T.rt[fa[p]],val[fa[p]]-b[son[fa[p]]]);
				chg(fa[p]);
			}
		}
		else printf("%d\n", (get(x)<get(y))||(get(x)==get(y)&&y>x));
		
//		for(int i=1;i<=n;++i) cout<<get(i)<<" "; cout<<"\n";
		
	}

	return 0;
}
/*
5 3
1 1 1 3 
4 3 4 2 1 
1 2 1 4 3 

1 1 1 1
1 4 4 1
2 1 5

start coding at 20:45.
finish it at 21:43.
*/ 

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 0ms
memory: 16296kb

input:

20 500
1 1 3 1 3 5 6 6 7 3 5 3 9 5 4 7 7 18 2
42129194 82765784 1447057 29726963 82321558 32094641 22474113 49277574 27527633 20746795 47630926 92888389 26787144 80703040 43876864 97991729 12117966 75633318 33577855 93462601
69163546 49621952 45236756 46447931 34085269 55246550 54414402 99593046 103...

output:

0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
0
0
1
1
0
1
1
1
0
1
1
0
0
0
0
1
1
1
1
1
1
0
1
0
0
1
0
1
1
0
0
0
1
1
1
1
1
1
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
0
1
1
0
1
0
0
1
0
0
1
1
1
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
1
0
1
0
0
1
1
1
1
0
0
1
0
0
0
1
0
1
1
1
...

result:

ok 238 numbers

Test #2:

score: 0
Wrong Answer
time: 2ms
memory: 16224kb

input:

20 500
1 1 3 1 3 5 3 4 2 4 3 12 6 7 12 6 4 11 10
2 0 2 1 1 1 2 0 2 2 1 0 0 2 1 0 1 0 1 1
0 0 2 0 0 0 1 2 2 2 0 2 2 2 1 0 1 0 1 1
2 5 2
1 6 1 0
1 7 1 1
2 5 11
2 18 16
2 13 7
2 4 3
1 6 0 0
1 5 0 2
2 16 12
2 5 18
2 8 16
1 4 0 0
2 5 2
1 19 2 2
1 10 0 0
1 15 2 2
2 12 14
1 12 1 1
1 13 1 2
1 3 2 2
1 6 2 2
...

output:

0
1
0
1
1
1
1
1
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
1
1
1
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
1
0
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
1
1
1
0
0
0
1
0
1
0
0
1
0
1
1
0
0
0
0
0
0
1
1
1
1
1
0
0
1
0
0
1
1
0
1
1
0
0
1
1
1
1
1
0
0
1
0
1
0
0
1
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
0
0
0
0
1
1
0
1
0
1
0
0
...

result:

wrong answer 113th numbers differ - expected: '0', found: '1'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #13:

score: 0
Wrong Answer
time: 77ms
memory: 28676kb

input:

200 200000
1 2 3 3 5 3 1 6 2 9 11 5 5 2 4 9 17 8 1 4 10 20 18 20 23 13 16 28 15 4 6 27 26 11 30 25 10 2 13 23 25 35 4 8 40 43 36 26 7 27 45 35 14 31 54 45 9 8 9 54 16 32 62 9 29 2 43 39 34 39 27 2 52 56 6 9 48 26 66 28 35 57 79 13 71 61 38 43 80 26 61 26 79 1 24 64 79 15 41 42 56 55 6 24 92 43 89 76...

output:

0
0
0
0
1
1
1
1
1
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
0
1
1
0
1
1
0
1
0
0
1
1
1
1
1
0
0
0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
0
1
1
0
1
1
1
1
1
1
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
0
0
1
1
1
1
0
1
0
0
1
0
1
0
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
0
1
1
1
1
0
0
1
0
0
1
0
1
0
0
...

result:

wrong answer 798th numbers differ - expected: '0', found: '1'

Subtask #4:

score: 0
Wrong Answer

Test #18:

score: 25
Accepted
time: 65ms
memory: 22520kb

input:

200 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
0
0
0
0
0
1
1
1
0
0
0
0
0
1
0
1
0
0
1
0
1
0
1
1
1
1
0
1
0
0
0
1
1
1
0
0
0
1
1
1
1
0
0
1
0
0
1
0
0
1
1
0
0
0
0
0
1
1
1
1
1
0
1
0
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
0
1
1
0
0
1
1
0
1
0
1
1
1
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
1
1
0
1
0
1
1
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
...

result:

ok 99788 numbers

Test #19:

score: 25
Accepted
time: 137ms
memory: 22376kb

input:

200 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

0
1
1
1
0
0
1
1
1
1
0
0
0
0
0
0
1
1
1
1
1
0
1
0
1
0
0
0
1
1
0
1
0
1
1
1
1
0
1
0
0
1
1
0
0
0
1
1
1
1
0
1
0
1
1
0
0
0
1
0
0
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
0
1
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
0
0
1
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
0
1
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
1
0
...

result:

ok 99818 numbers

Test #20:

score: 25
Accepted
time: 200ms
memory: 24536kb

input:

2000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
0
1
1
1
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
0
0
1
1
1
1
0
1
1
1
0
0
1
1
1
1
1
0
1
1
0
1
0
1
1
0
0
1
1
1
0
0
0
1
1
1
1
1
1
1
0
1
0
1
1
0
1
1
0
1
1
0
1
1
0
0
1
0
0
1
0
1
0
0
1
1
0
0
0
0
1
0
0
1
1
1
1
0
0
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
0
0
1
1
0
0
1
1
1
1
1
1
0
1
0
0
0
1
0
1
0
0
1
1
1
1
0
1
0
...

result:

ok 100002 numbers

Test #21:

score: 25
Accepted
time: 308ms
memory: 30468kb

input:

20000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
1
0
1
1
1
0
0
0
1
0
1
1
0
0
0
1
1
1
1
1
0
1
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
1
1
0
0
0
1
0
0
0
0
0
0
1
1
1
1
0
1
0
1
1
1
0
0
0
0
1
0
0
0
1
1
0
0
0
1
1
1
1
0
0
0
1
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
0
1
0
1
1
1
0
1
0
0
0
1
0
0
0
0
...

result:

ok 99886 numbers

Test #22:

score: 25
Accepted
time: 680ms
memory: 54644kb

input:

200000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1
1
0
1
1
0
1
0
0
0
0
1
0
1
1
1
1
1
0
1
1
0
0
0
0
1
0
0
0
1
1
0
0
1
1
1
0
1
0
1
0
0
1
0
0
0
1
1
1
0
1
1
0
1
0
0
0
0
1
1
1
0
0
1
1
0
0
1
0
0
1
0
1
0
0
1
0
0
0
0
1
0
1
0
1
1
0
0
1
0
0
0
1
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
0
1
1
0
1
1
0
1
1
1
0
1
1
0
1
0
0
1
0
1
0
1
0
1
1
1
0
1
0
...

result:

ok 100006 numbers

Test #23:

score: 25
Accepted
time: 650ms
memory: 55032kb

input:

200000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1
1
0
0
1
1
1
0
0
0
1
1
1
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
1
1
1
0
1
1
1
0
0
0
1
0
0
1
0
1
0
0
1
1
1
0
0
1
0
0
1
0
0
0
1
1
1
0
0
1
0
1
1
0
0
1
0
0
0
1
1
0
1
1
0
1
1
1
0
0
0
0
0
0
1
1
0
0
0
1
1
0
1
0
0
0
1
1
1
0
1
1
1
1
1
1
0
0
1
0
1
0
1
0
...

result:

ok 99439 numbers

Test #24:

score: 0
Wrong Answer
time: 752ms
memory: 54260kb

input:

200000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1
1
1
1
1
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
0
1
1
0
0
1
1
0
1
1
1
1
1
0
0
0
0
1
0
0
1
0
0
1
0
1
1
1
0
0
1
1
1
0
1
1
1
1
0
1
0
0
1
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
0
0
0
1
1
0
1
1
0
1
0
1
1
0
1
1
1
0
1
1
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
1
1
0
0
1
1
1
0
1
0
0
1
0
0
1
0
1
1
0
1
0
...

result:

wrong answer 65596th numbers differ - expected: '0', found: '1'

Subtask #5:

score: 20
Accepted

Test #26:

score: 20
Accepted
time: 32ms
memory: 16200kb

input:

200 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 1...

output:

1
0
1
0
1
1
1
1
0
1
1
1
0
0
0
0
1
0
1
1
0
1
0
0
1
1
1
0
1
0
0
0
1
0
1
1
0
0
0
1
1
1
0
0
1
1
1
0
1
0
0
1
0
1
1
0
1
1
0
0
1
0
0
1
0
0
0
1
0
1
0
0
1
1
1
1
1
1
1
0
0
0
1
0
0
1
0
0
1
1
1
1
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
1
0
0
0
0
1
1
1
0
1
0
1
1
1
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
1
1
1
0
1
1
1
0
...

result:

ok 100455 numbers

Test #27:

score: 20
Accepted
time: 33ms
memory: 16180kb

input:

200 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 1...

output:

0
1
0
0
1
0
0
0
0
0
1
1
0
0
1
1
0
0
1
1
0
1
1
0
1
0
0
0
0
1
1
1
0
0
1
0
1
1
1
1
0
0
0
1
1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1
0
0
0
0
1
1
0
1
0
1
0
1
1
1
0
0
0
1
0
1
0
1
1
1
1
0
1
0
0
0
1
0
0
0
1
1
0
0
1
0
1
0
1
1
0
0
0
1
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
1
0
0
1
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
0
0
1
1
1
1
0
0
...

result:

ok 99902 numbers

Test #28:

score: 20
Accepted
time: 50ms
memory: 16632kb

input:

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

output:

0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
1
1
0
0
1
0
1
1
0
0
1
0
0
1
0
0
1
1
1
1
0
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
1
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
0
0
0
1
0
1
1
0
0
1
0
0
1
0
1
1
1
...

result:

ok 99882 numbers

Test #29:

score: 20
Accepted
time: 63ms
memory: 20404kb

input:

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

output:

0
0
0
0
1
0
0
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
0
0
1
0
1
0
0
1
1
1
1
0
0
1
1
1
0
1
1
0
1
1
0
0
0
0
1
0
1
0
1
1
0
0
0
1
0
0
1
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
1
0
1
0
1
0
1
0
0
1
0
0
1
1
0
0
0
1
1
0
0
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
1
1
1
0
1
1
0
1
0
0
1
1
1
0
1
0
1
0
1
0
0
1
0
1
0
1
...

result:

ok 100151 numbers

Test #30:

score: 20
Accepted
time: 136ms
memory: 71484kb

input:

200000 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 9...

output:

0
0
1
0
1
1
1
0
0
1
0
1
0
0
1
0
1
1
1
1
0
0
1
0
1
1
0
1
1
0
0
1
1
0
0
1
0
1
1
1
1
0
0
1
0
0
0
1
1
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
1
0
0
1
0
0
1
1
0
1
0
1
0
0
1
1
1
0
1
0
0
0
0
0
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
0
1
1
1
1
1
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
1
0
0
1
0
1
0
0
1
1
0
0
1
0
0
0
...

result:

ok 100291 numbers

Test #31:

score: 20
Accepted
time: 132ms
memory: 72708kb

input:

200000 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 9...

output:

0
1
1
0
0
0
0
1
1
0
0
1
0
1
1
1
1
1
1
0
1
0
0
0
1
0
0
1
1
1
0
0
1
0
0
0
1
0
0
1
1
0
1
1
1
0
1
0
1
1
1
1
0
1
0
1
1
0
0
0
0
1
0
0
0
1
0
0
1
1
0
1
0
1
1
1
0
1
1
1
1
0
1
0
1
1
1
1
0
0
1
0
0
1
0
1
1
0
1
1
1
0
0
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
1
0
1
1
0
1
0
1
0
1
0
0
0
0
1
0
0
1
1
1
1
...

result:

ok 100358 numbers

Test #32:

score: 20
Accepted
time: 115ms
memory: 70848kb

input:

200000 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 9...

output:

1
0
0
1
1
0
1
0
1
1
1
0
0
1
1
1
1
0
1
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
0
1
0
0
0
1
1
0
1
1
1
0
1
1
1
0
1
0
1
0
0
1
1
0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
0
1
1
1
1
0
1
0
1
1
0
1
1
0
0
1
1
0
0
1
0
1
0
0
0
1
0
1
1
1
0
1
0
1
0
1
1
0
0
0
1
1
0
1
1
1
1
0
1
1
0
1
0
0
1
0
0
...

result:

ok 66538 numbers

Subtask #6:

score: 0
Skipped

Dependency #1:

0%