QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562085#8222. 投票游戏Idtwtei20 137ms88984kbC++203.5kb2024-09-13 14:54:052024-09-13 14:54:05

Judging History

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

  • [2024-09-13 14:54:05]
  • 评测
  • 测评结果:20
  • 用时:137ms
  • 内存:88984kb
  • [2024-09-13 14:54:05]
  • 提交

answer

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

#define 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,fa[N];
vector<int> G[N];

ll f[N],a[N],b[N],val[N]; int rt[N];
struct FHQ{
	#define lc t[id].ls
	#define rc t[id].rs
	struct TREE{ int ls,rs,rid; ll sum,mn; }t[N];
	void psu(int id){ t[id].sum=t[lc].sum+b[id]+t[rc].sum,t[id].mn=min({t[lc].mn,t[lc].sum+f[id],t[lc].sum+b[id]+t[rc].mn}); }
	void spl(int id,int &x,int &y,ll v,int o){
		if(!id) return x=y=0,void();
		if(f[id]>v||(f[id]==v&&id>o)) x=id,spl(rc,rc,y,v,o),psu(x);
		else y=id,spl(lc,x,lc,v,o),psu(y);
	}
	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),psu(x),x;
		else return t[y].ls=mer(x,t[y].ls),psu(y),y;
	}
	ll bry(int id,ll v){
		if(!id) return v;
		if(t[lc].mn<v) return bry(lc,v);
		else if(t[lc].sum+f[id]<v) return v-t[lc].sum;
		else return bry(rc,v-t[lc].sum-b[id]);
	}
	void ins(int u,int v){ int x,y; spl(rt[u],x,y,f[v],v),t[v].mn=f[v],t[v].sum=b[v],rt[u]=mer(x,mer(v,y)); }
	void era(int u,int v){ int x,y,z; spl(rt[u],x,z,f[v],v),spl(x,x,y,f[v],v+1),rt[u]=mer(x,z); }
	#undef lc
	#undef rc
}T;

struct SEG{
	ll 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; }
}sg[N];
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,const SEG &v){
		if(l==r) return t[id]=v,void();
		ql<=mid?chg(lc,l,mid,ql,v):chg(rc,mid+1,r,ql,v); 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;

int siz[N],son[N],top[N],btm[N],dfn[N],d_c=0;
SEG fsg(int u){
	if(!son[u]) return {0,0,a[u]};
	ll w=T.bry(rt[u],a[u]+val[u]);
	return {w,w,T.bry(rt[u],a[u]+val[u]-b[son[u]])};
}
ll ff(int u){ return S.ask(1,1,n,dfn[u],dfn[btm[top[u]]]).get(0); }
void dfs0(int u){
	siz[u]=1;
	for(int v:G[u]){
		dfs0(v),siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v;
	}
	for(int v:G[u]) if(v^son[u]) T.ins(u,v);
	sg[u]=fsg(u),f[u]=sg[u].get(f[son[u]]);
}
void dfs1(int u,int tp){
	dfn[u]=++d_c,btm[top[u]=tp]=u,S.chg(1,1,n,dfn[u],sg[u]);
	if(son[u]) dfs1(son[u],tp);
	for(int v:G[u]) if(v^son[u]) dfs1(v,v);
}
void chg(int x){
	for(;x;x=fa[x]){
		sg[x]=fsg(x),S.chg(1,1,n,dfn[x],sg[x]);
		x=top[x]; if(!fa[x]) return;
		T.era(fa[x],x),f[x]=ff(x),T.ins(fa[x],x);
	}
}

int main(){
	
	n=rd,m=rd;
	for(int i=2;i<=n;++i) G[fa[i]=rd].pb(i);
	for(int i=1;i<=n;++i) a[i]=rd;
	for(int i=1;i<=n;++i) b[i]=rd;
	for(int i=2;i<=n;++i) val[fa[i]]+=b[i];
	
	for(int i=1;i<=n;++i) T.t[i].rid=rnd(); T.t[0].mn=INF;
	
	dfs0(1),dfs1(1,1);
	
	for(int i=1,op,u,x,y;i<=m;++i){
		op=rd; if(op==1) u=rd,x=rd,y=rd; else x=rd,y=rd;
		if(op==1){
			a[u]=x,chg(u);
			if(!fa[u]) continue;
			val[fa[u]]+=y-b[u];
			if(u!=son[fa[u]]) T.era(fa[u],u),b[u]=y,f[u]=ff(u),T.ins(fa[u],u);
			else b[u]=y;
			chg(fa[u]);
		}
		else{ ll wx=ff(x),wy=ff(y); printf("%d\n", (wx<wy)||(wx==wy&&x<y)); }
	}
	
	return 0;
	
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Memory Limit Exceeded

Test #1:

score: 0
Memory Limit Exceeded

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:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #13:

score: 0
Time Limit Exceeded

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:


result:


Subtask #4:

score: 0
Memory Limit Exceeded

Test #18:

score: 0
Memory Limit Exceeded

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:


result:


Subtask #5:

score: 20
Accepted

Test #26:

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

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: 30ms
memory: 18308kb

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: 45ms
memory: 18800kb

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: 64ms
memory: 27372kb

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: 137ms
memory: 88972kb

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: 137ms
memory: 88972kb

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: 102ms
memory: 88984kb

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%