QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #580756 | #9373. Query on Tree | Afterlife | WA | 71ms | 26172kb | C++20 | 8.4kb | 2024-09-21 23:41:26 | 2024-09-21 23:41:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+1e3+7,K=10,INF=1e18;
struct T {
vector<int> _;
int cnt;
struct Node {
int l,r,ls,rs,tag,mx,sum;
}t[N*2+1];
void Add(int x,int v)
{
t[x].tag+=v;
t[x].mx+=v;
t[x].sum+=v;
}
void update(int x)
{
t[x].mx=max(t[t[x].ls].mx,t[t[x].rs].mx);
t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
}
void pushdown(int x)
{
if(t[x].tag)
{
Add(t[x].ls,t[x].tag);
Add(t[x].rs,t[x].tag);
t[x].tag=0;
}
}
int build(int l,int r,vector<int> &a)
{
int x=++cnt;
t[x].l=l,t[x].r=r;
t[x].tag=0;
if(l==r)
{
t[x].mx=a[l];
t[x].sum=0;
return x;
}
int mid=(l+r)>>1;
t[x].ls=build(l,mid,a);
t[x].rs=build(mid+1,r,a);
update(x);
return x;
}
void init(int n,vector<int> a)
{
cnt=0;
build(1,n,a);
}
void change(int x,int l,int r,int v)
{
if(l<=t[x].l&&t[x].r<=r)
{
Add(x,v);
return;
}
int mid=(t[x].l+t[x].r)>>1;
pushdown(x);
if(l<=mid)
change(t[x].ls,l,r,v);
if(r>mid)
change(t[x].rs,l,r,v);
update(x);
}
int qsum(int x,int p)
{
if(t[x].l==t[x].r)
return t[x].sum;
int mid=(t[x].l+t[x].r)>>1;
pushdown(x);
if(p<=mid)
return qsum(t[x].ls,p);
else
return qsum(t[x].rs,p);
}
void setv(int x,int p,int v)
{
if(t[x].l==t[x].r)
{
t[x].sum=0;
t[x].mx=v;
return;
}
int mid=(t[x].l+t[x].r)>>1;
pushdown(x);
if(p<=mid)
setv(t[x].ls,p,v);
else
setv(t[x].rs,p,v);
update(x);
}
int qmx(int x,int l,int r)
{
if(l<=t[x].l&&t[x].r<=r)
return t[x].mx;
pushdown(x);
int mid=(t[x].l+t[x].r)>>1;
int ret=LLONG_MIN;
if(l<=mid)
ret=max(ret,qmx(t[x].ls,l,r));
if(r>mid)
ret=max(ret,qmx(t[x].rs,l,r));
return ret;
}
}A,B;
int T;
int n,q,a[N],bc,dc;
int bfn[N],dfn[N],ds[N],bs[N],fa[N];
int lp[N][K+1],rp[N][K+1];
int mk[N][K+1],jmp[N][K+1],dep[N],st[N],ed[N];
vector<int> g[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i],g[i].clear();
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
{
bc=0;
for(int i=1;i<=n;i++)
bfn[i]=0;
queue<int> q;
q.push(1);
while(!q.empty())
{
int x=q.front();
q.pop();
bfn[x]=++bc;
bs[bc]=x;
for(auto v:g[x])
{
if(v==fa[x])
continue;
fa[v]=x;
dep[v]=dep[x]+1;
q.push(v);
}
}
}
{
auto dfs=[&](auto self,int x,int f) ->void
{
dfn[x]=++dc;
ds[dc]=x;
st[x]=dc;
for(auto v:g[x])
{
if(v==f)
continue;
self(self,v,x);
}
ed[x]=dc;
};
dc=0;
dfs(dfs,1,0);
}
for(int i=n;i>=1;i--)
{
int x=bs[i];
for(int j=1;j<=K;j++)
lp[x][j]=n+1,rp[x][j]=0,mk[x][j]=-INF;
lp[x][0]=rp[x][0]=i;
mk[x][0]=a[x];
for(auto v:g[x])
{
if(v==fa[x])
continue;
for(int j=1;j<=K;j++)
{
lp[x][j]=min(lp[x][j],lp[v][j-1]);
rp[x][j]=max(rp[x][j],rp[v][j-1]);
mk[x][j]=max(mk[x][j],mk[v][j-1]);
}
}
}
for(int i=1;i<=n;i++)
{
int x=bs[i];
jmp[x][0]=x;
jmp[x][1]=fa[x];
for(int j=2;j<=K;j++)
jmp[x][j]=jmp[jmp[x][j-1]][1];
}
vector<int> tmp(n+1);
for(int i=1;i<=n;i++)
tmp[i]=a[bs[i]];
A.init(n,tmp);
for(int i=1;i<=n;i++)
tmp[i]=mk[ds[i]][K];
B.init(n,tmp);
auto push=[&](const int &x)
{
if(!x)
return;
if(lp[x][K]<=rp[x][K])
{
int t=B.qsum(1,dfn[x]);
A.change(1,lp[x][K],rp[x][K],t);
}
};
auto upd=[&](const int &x)
{
if(!x)
return;
if(lp[x][K]<=rp[x][K])
B.setv(1,dfn[x],A.qmx(1,lp[x][K],rp[x][K]));
};
while(q--)
{
int op;
cin>>op;
int ans=LLONG_MIN;
if(op==1)
{
int x,d,v;
cin>>x>>d>>v;
{
int L=lp[x][d],R=rp[x][d];
push(jmp[x][K-d]);
if(L<=R)
{
A.change(1,L,R,v);
ans=max(ans,A.qmx(1,L,R));
}
upd(jmp[x][K-d]);
}
for(int u=fa[x],z=x;u;z=u,u=fa[u])
{
int rd=d-(dep[x]-dep[u]);
if(rd<0)
break;
int L=lp[u][rd],R=rp[u][rd];
push(jmp[u][K-rd]);
if(!rd)
{
if(L<=R)
A.change(1,L,R,v),ans=max(ans,A.qmx(1,L,R));
}
else
{
int lu=lp[z][rd-1],ru=rp[z][rd-1];
if(L<=lu-1)
A.change(1,L,lu-1,v),ans=max(ans,A.qmx(1,L,lu-1));
if(ru+1<=R)
A.change(1,ru+1,R,v),ans=max(ans,A.qmx(1,ru+1,R));
}
upd(jmp[u][K-rd]);
}
}
else if(op==2)
{
vector<int>L(K*2+5,n+1),R(K*2+5,0);
int S=K+1;
int x,d,v;
cin>>x>>d>>v;
for(int u=x;u;u=fa[u])
{
int rd=d-(dep[x]-dep[u]);
if(rd<0)
break;
for(int j=0;j<=rd;j++)
{
L[dep[u]+j-dep[x]+S]=min(L[dep[u]+j-dep[x]+S],lp[u][j]);
R[dep[u]+j-dep[x]+S]=max(R[dep[u]+j-dep[x]+S],rp[u][j]);
}
}
for(int j=0;j<L.size();j++)
{
if(L[j]>R[j])
continue;
int u=bs[L[j]];
push(jmp[u][K]);
A.change(1,L[j],R[j],v);
upd(jmp[u][K]);
ans=max(ans,A.qmx(1,L[j],R[j]));
}
}
else if(op==3)
{
int x,v;
cin>>x>>v;
for(int j=0;j<K;j++)
{
int u=jmp[x][K-j];
push(u);
if(lp[x][j]<=rp[x][j])
{
A.change(1,lp[x][j],rp[x][j],v);
ans=max(ans,A.qmx(1,lp[x][j],rp[x][j]));
}
upd(u);
}
B.change(1,st[x],ed[x],v);
ans=max(ans,B.qmx(1,st[x],ed[x]));
}
if(ans<-1e15)
cout<<"GG\n";
else
cout<<ans<<"\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 24132kb
input:
1 5 5 1 2 1 3 2 1 2 2 3 2 4 4 5 2 2 1 0 1 2 1 3 3 4 -5 2 5 2 3 3 2 -1
output:
3 6 1 5 4
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 68ms
memory: 26172kb
input:
10000 3 9 42973045452542 34994498886390 -91733395797555 1 3 1 2 1 1 5 -71952967 3 1 -816873082 1 1 5 -842437577 2 3 7 254550528 3 3 -854082700 2 3 2 699808309 3 3 554885567 1 2 7 595565507 1 3 0 -318374053 3 2 -63158159333100 77264362049163 -99188430131116 1 2 3 2 2 2 4 -305866230 3 1 -549738403 3 5...
output:
GG 42972228579460 GG 42972483129988 -91734812202809 42973182938297 -91733557508933 GG -91733875882986 77264056182933 77263506444530 7065382376488 7065749360235 7066534912965 -85115611272570 -85114714781312 96492412785032 -20428913156111 -20428197540063 96491742171666 -14945310996805 96491180203461 -...
result:
ok 200000 lines
Test #3:
score: -100
Wrong Answer
time: 71ms
memory: 24060kb
input:
10000 4 32 -1057044448491 -93293078803919 -24212938548357 74427756948193 1 3 1 2 3 4 3 1 -82365883 1 2 9 -730670945 2 4 2 -618745828 2 1 2 774032949 3 3 6733210 3 3 -843683844 3 1 327410390 3 1 -865685600 1 4 6 -951367966 3 2 107763506 1 3 2 721870187 2 3 3 -530847597 2 2 1 451029291 3 2 231297873 3...
output:
74427674582310 GG 74427055836482 74427829869431 74427836602641 74426992918797 74427320329187 74426454643587 GG -93292817648557 -93292095778370 74425923795990 -1057589620769 -93291944298803 74425228504438 74425430401539 -93291936231808 74425906008467 GG -1058067327518 74424997886529 74424370598990 74...
result:
wrong answer 234th lines differ - expected: '-78585193822704', found: '97686244528495'