QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562087 | #8222. 投票游戏 | Idtwtei | 20 | 133ms | 95836kb | C++20 | 3.5kb | 2024-09-13 14:55:27 | 2024-09-13 14:55:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
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,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);
}
}
signed 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("%lld\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: 29ms
memory: 20292kb
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: 20352kb
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: 46ms
memory: 20832kb
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: 62ms
memory: 31676kb
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: 131ms
memory: 95836kb
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: 133ms
memory: 92756kb
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: 117ms
memory: 95308kb
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%