QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #177431 | #4914. Slight Hope | zhouhuanyi | Compile Error | / | / | C++14 | 3.9kb | 2023-09-12 22:59:12 | 2023-09-12 22:59:13 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 250000
#define M 500
#define mod 998244353
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
void Adder(int &x,int d)
{
x+=d;
if (x>=mod) x-=mod;
return;
}
void Adder2(int &x,int d)
{
x+=d;
if (x<0) x+=mod;
return;
}
int MD(int x)
{
return x>=mod?x-mod:x;
}
int MD2(int x)
{
return x<0?x+mod:x;
}
int n,q,leng,leng2,maxn,sz,ans,a[N+1],s[N+1],DP[N+1],DP2[N+1],fa[N+1],block[N+1],depth[N+1],cnt[N+1],L[N+1],R[N+1],sl[N+1],sr[N+1],delta[N+1],F[N+1],dp[M+1][N+1],nt[N+1],nt2[N+1],leng[N+1],leng2[N+1],ls[N+1],ls2[N+1],hs[N+1],top[N+1],sz[N+1],hs2[N+1],top2[N+1],sz2[N+1],dfn[N+1],rev[N+1],dfn2[N+1],rev2[N+1];
vector<int>E[N+1];
int find(int x,int d)
{
while (nt[top[x]]&&depth[nt[top[x]]]>=d) x=nt[top[x]];
return rev[dfn[top[x]]+d-depth[top[x]]];
}
int find2(int x,int d)
{
while (nt2[top2[x]]&&depth[nt2[top2[x]]]>=d) x=nt2[top2[x]];
return rev2[dfn2[top[x]]+d-depth[top2[x]]];
}
int calc(int x,int d)
{
int l=find(x,depth[d]),r=find2(x,depth[d]),rst=MD2(MD2(DP2[x]-DP2[nt2[r]])-MD2(DP[x]-DP[nt[l]]));
if (d<l) Adder2(rst,-MD2(s[r]-s[l-1]));
else if (d<r) Adder2(rst,-MD2(s[r]-s[d]));
return 1ll*rst*rst%mod;
}
int query(int l,int r,int d)
{
int res=0;
if (block[r]-block[l]<=1)
{
for (int i=l;i<=r;++i) Adder(res,calc(i,d));
}
else
{
for (int i=l;i<=min(block[l]*sz,n);++i) Adder(res,calc(i,d));
for (int i=block[l]+1;i<=block[r]-1;++i) Adder(res,F[i][d]);
for (int i=(block[r]-1)*sz+1;i<=r;++i) Adder(res,calc(i,d));
return res;
}
}
void dfs(int x)
{
sz[x]=1;
for (int i=0;i<E[x].size();++i)
{
dfs(E[x][i]),sz[x]+=sz[E[x][i]];
if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
}
return;
}
void dfs2(int x)
{
dfn[x]=++leng;
if (hs[x]) top[hs[x]]=top[x],dfs2(hs[x]);
for (int i=0;i<E[x].size();++i)
if (E[x][i]!=hs[x])
top[E[x][i]]=E[x][i],dfs2(E[x][i]);
return;
}
void dfs3(int x)
{
sz2[x]=1;
for (int i=0;i<E2[x].size();++i)
{
dfs3(E2[x][i]),sz2[x]+=sz2[E2[x][i]];
if (sz2[E2[x][i]]>sz2[hs2[x]]) hs2[x]=E2[x][i];
}
return;
}
void dfs4(int x)
{
dfn2[x]=++leng2;
if (hs2[x]) top2[hs2[x]]=top2[x],dfs4(hs2[x]);
for (int i=0;i<E2[x].size();++i)
if (E2[x][i]!=hs2[x])
top2[E2[x][i]]=E2[x][i],dfs4(E2[x][i]);
return;
}
int main()
{
int pv;
n=read(),q=read(),sz=sqrt(n),depth[1]=1;
while ((n-1)/sz+1>M) sz++;
for (int i=1;i<=n;++i) block[i]=(i-1)/sz+1;
for (int i=1;i<=n;++i) a[i]=read(),s[i]=MD(s[i-1]+a[i]),R[i]=-1;
depth[1]=1;
for (int i=2;i<=n;++i)
{
fa[i]=read(),depth[i]=depth[fa[i]]+1,R[fa[i]]=i;
if (!L[fa[i]]) L[fa[i]]=i;
}
maxn=depth[n];
for (int i=1;i<=n;++i)
{
sr[depth[i]]=i;
if (!sl[depth[i]]) sl[depth[i]]=i;
}
for (int i=1;i<=maxn;++i)
if (block[sl[i]]+1<=block[sr[i]]-1)
{
for (int j=block[sl[i]]+1;j<=block[sr[i]]-1;++j)
{
for (int k=(j-1)*sz+1;k<=min(j*sz,n);++k) F[k]=k,delta[k]=0;
for (int k=min(j*sz,n)+1;k<=n;++k) F[k]=F[fa[k]];
for (int k=(j-1)*sz+1;k<=min(j*sz,n);++k) dp[j][k]=MD(dp[i][k-1]+(2ll*delta[F[k]]+a[k])*a[k]%mod),Adder(delta[F[k]],a[k]);
}
}
for (int i=1;i<=n;++i)
{
pv=0;
for (int j=R[i];j>=L[i];--j)
{
nt[i]=pv;
if (L[j]<=R[j]) pv=j;
}
pv=0;
for (int j=L[i];j<=R[i];++j)
{
nt2[i]=pv;
if (L[j]<=R[j]) pv=j;
}
}
for (int i=n;i>=1;--i) DP[i]=DP[nt[i]]+s[i-1],DP2[i]=DP2[nt2[i]]+s[i];
for (int i=1;i<=n;++i)
{
if (nt[i]) E[nt[i]].push_back(i);
if (nt2[i]) E[nt2[i]].push_back(i);
}
for (int i=1;i<=n;++i)
{
if (!nt[i]) dfs(i),dfs2(i);
if (!nt2[i]) dfs3(i),dfs4(i);
}
while (q--)
{
l=read()^ans,r=read()^ans,ans=query(l,sr[depth[l]],r);
if (depth[l]!=maxn&&sl[depth[l]+1]<=L[l]-1) Adder(ans,query(sl[depth[l]+1],L[l]-1,r));
printf("%d\n",ans);
}
return 0
}
Details
answer.code:36:180: error: conflicting declaration ‘int leng [250001]’
36 | int n,q,leng,leng2,maxn,sz,ans,a[N+1],s[N+1],DP[N+1],DP2[N+1],fa[N+1],block[N+1],depth[N+1],cnt[N+1],L[N+1],R[N+1],sl[N+1],sr[N+1],delta[N+1],F[N+1],dp[M+1][N+1],nt[N+1],nt2[N+1],leng[N+1],leng2[N+1],ls[N+1],ls2[N+1],hs[N+1],top[N+1],sz[N+1],hs2[N+1],top2[N+1],sz2[N+1],dfn[N+1],rev[N+1],dfn2[N+1],rev2[N+1];
| ^~~~
answer.code:36:9: note: previous declaration as ‘int leng’
36 | int n,q,leng,leng2,maxn,sz,ans,a[N+1],s[N+1],DP[N+1],DP2[N+1],fa[N+1],block[N+1],depth[N+1],cnt[N+1],L[N+1],R[N+1],sl[N+1],sr[N+1],delta[N+1],F[N+1],dp[M+1][N+1],nt[N+1],nt2[N+1],leng[N+1],leng2[N+1],ls[N+1],ls2[N+1],hs[N+1],top[N+1],sz[N+1],hs2[N+1],top2[N+1],sz2[N+1],dfn[N+1],rev[N+1],dfn2[N+1],rev2[N+1];
| ^~~~
answer.code:36:190: error: conflicting declaration ‘int leng2 [250001]’
36 | int n,q,leng,leng2,maxn,sz,ans,a[N+1],s[N+1],DP[N+1],DP2[N+1],fa[N+1],block[N+1],depth[N+1],cnt[N+1],L[N+1],R[N+1],sl[N+1],sr[N+1],delta[N+1],F[N+1],dp[M+1][N+1],nt[N+1],nt2[N+1],leng[N+1],leng2[N+1],ls[N+1],ls2[N+1],hs[N+1],top[N+1],sz[N+1],hs2[N+1],top2[N+1],sz2[N+1],dfn[N+1],rev[N+1],dfn2[N+1],rev2[N+1];
| ^~~~~
answer.code:36:14: note: previous declaration as ‘int leng2’
36 | int n,q,leng,leng2,maxn,sz,ans,a[N+1],s[N+1],DP[N+1],DP2[N+1],fa[N+1],block[N+1],depth[N+1],cnt[N+1],L[N+1],R[N+1],sl[N+1],sr[N+1],delta[N+1],F[N+1],dp[M+1][N+1],nt[N+1],nt2[N+1],leng[N+1],leng2[N+1],ls[N+1],ls2[N+1],hs[N+1],top[N+1],sz[N+1],hs2[N+1],top2[N+1],sz2[N+1],dfn[N+1],rev[N+1],dfn2[N+1],rev2[N+1];
| ^~~~~
answer.code:36:235: error: conflicting declaration ‘int sz [250001]’
36 | int n,q,leng,leng2,maxn,sz,ans,a[N+1],s[N+1],DP[N+1],DP2[N+1],fa[N+1],block[N+1],depth[N+1],cnt[N+1],L[N+1],R[N+1],sl[N+1],sr[N+1],delta[N+1],F[N+1],dp[M+1][N+1],nt[N+1],nt2[N+1],leng[N+1],leng2[N+1],ls[N+1],ls2[N+1],hs[N+1],top[N+1],sz[N+1],hs2[N+1],top2[N+1],sz2[N+1],dfn[N+1],rev[N+1],dfn2[N+1],rev2[N+1];
| ^~
answer.code:36:25: note: previous declaration as ‘int sz’
36 | int n,q,leng,leng2,maxn,sz,ans,a[N+1],s[N+1],DP[N+1],DP2[N+1],fa[N+1],block[N+1],depth[N+1],cnt[N+1],L[N+1],R[N+1],sl[N+1],sr[N+1],delta[N+1],F[N+1],dp[M+1][N+1],nt[N+1],nt2[N+1],leng[N+1],leng2[N+1],ls[N+1],ls2[N+1],hs[N+1],top[N+1],sz[N+1],hs2[N+1],top2[N+1],sz2[N+1],dfn[N+1],rev[N+1],dfn2[N+1],rev2[N+1];
| ^~
answer.code:37:1: error: ‘vector’ does not name a type
37 | vector<int>E[N+1];
| ^~~~~~
answer.code: In function ‘int query(int, int, int)’:
answer.code:65:72: error: invalid types ‘int[int]’ for array subscript
65 | for (int i=block[l]+1;i<=block[r]-1;++i) Adder(res,F[i][d]);
| ^
answer.code: In function ‘void dfs(int)’:
answer.code:72:11: error: invalid types ‘int[int]’ for array subscript
72 | sz[x]=1;
| ^
answer.code:73:24: error: ‘E’ was not declared in this scope
73 | for (int i=0;i<E[x].size();++i)
| ^
answer.code:75:32: error: invalid types ‘int[int]’ for array subscript
75 | dfs(E[x][i]),sz[x]+=sz[E[x][i]];
| ^
answer.code:76:35: error: invalid types ‘int[int]’ for array subscript
76 | if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
| ^
answer.code: In function ‘void dfs2(int)’:
answer.code:84:24: error: ‘E’ was not declared in this scope
84 | for (int i=0;i<E[x].size();++i)
| ^
answer.code: In function ‘void dfs3(int)’:
answer.code:92:24: error: ‘E2’ was not declared in this scope
92 | for (int i=0;i<E2[x].size();++i)
| ^~
answer.code: In function ‘void dfs4(int)’:
answer.code:103:24: error: ‘E2’ was not declared in this scope
103 | for (int i=0;i<E2[x].size();++i)
| ^~
answer.code: In function ‘int main()’:
answer.code:155:28: error: ‘E’ was not declared in this scope
155 | if (nt[i]) E[nt[i]].push_back(i);
| ^
answer.code:156:29: error: ‘E’ was not declared in this scope
156 | if (nt2[i]) E[nt2[i]].push_back(i);
| ^
answer.code:165:17: error: ‘l’...