QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #294317 | #7872. 崩坏天际线 | zhouhuanyi | Compile Error | / | / | C++20 | 4.7kb | 2023-12-30 11:55:35 | 2023-12-30 11:55:36 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define N 100000
#define mod 998244353
using namespace std;
const int inv2=(mod+1)>>1;
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;
}
struct reads
{
int l,r,t;
};
reads tong[N+1];
struct rds
{
int x,t;
};
rds st[N+1];
int n,q,sz,invpw[N+1],block[N+1],length,leng,delta[N+1],sdelta[N+1],ls[N+1],rs[N+1],pv[N+1],nt[N+1],sps[N+1],num[N+1],num2[N+1],snum[N+1],snum2[N+1],dque[N+1],top,tongs[N+1],lengths,sz[N+1],hs[N+1],belong[N+1],sbelong[N+1],sq[N+1],cater,cl[N+1],DP[N+1],s[N+1],s2[N+1],len;
vector<reads>v[N+1];
void dfs(int x,int l,int r)
{
pv[x]=l,nt[x]=r,sz[x]=1;
if (ls[x]) depth[ls[x]]=depth[x]+1,DP[ls[x]]=MD(DP[x]+invpw2[depth[ls[x]]]),dfs(ls[x],l,x);
if (rs[x]) depth[rs[x]]=depth[x]+1,DP[rs[x]]=MD(DP[x]+invpw2[depth[rs[x]]]),dfs(rs[x],x,r);
sz[x]=sz[ls[x]]+sz[rs[x]]+1,hs[x]=(sz[ls[x]]>sz[rs[x]])?ls[x]:rs[x];
return;
}
void dfs2(int x)
{
top[hs[x]]=top[x];
if (ls[x]^rs[x]^hs[x]) top[ls[x]^rs[x]^hs[x]]=ls[x]^rs[x]^hs[x];
if (ls[x]) dfs2(ls[x]);
if (rs[x]) dfs2(rs[x]);
return;
}
void dfs3(int x)
{
if (ls[x]) sdepth[ls[x]]=sdepth[x]+1,dfs3(ls[x]);
if (rs[x]) sdepth[rs[x]]=sdepth[x]+1,dfs3(rs[x]);
return;
}
int lca(int x,int y)
{
while (top[x]!=top[y])
{
if (depth[top[x]]<depth[top[y]]) swap(x,y);
x=fa[top[x]];
}
if (depth[x]>depth[y]) swap(x,y);
return x;
}
int calc(int l,int r,int sl,int sr,int d)
{
int res=1ll*(r-l)*invpw[d]%mod,rst=0,ds;
if (sl<=sr)
{
ds=lca(sl,sr);
Adder(rst,MD2(MD2(DP[sl]-DP[ds])-1ll*l*(depth[sl]-depth[ds])%mod));
Adder(rst,MD2(1ll*r*(depth[sr]-depth[ds])%mod-MD2(DP[sr]-DP[ds])));
Adder(rst,MD2(s[ds-1]-s[sl-1]));
Adder(rst,MD2(s2[sr]-s2[ds]));
Adder2(res,-1ll*rst*invpw[d]%mod*pw[depth[ds]-1]%mod);
}
return res;
}
int main()
{
int op,l,r,x,ps=0,ft,ed;
inv2=(mod+1)>>1,pw[0]=invpw[0]=1;
for (int i=1;i<=N;++i) pw[i]=2ll*pw[i-1]%mod,invpw[i]=1ll*invpw[i-1]*inv2%mod;
n=read(),q=read();
for (int i=1;i<=q;++i)
{
op=read();
if (op[i]==1) l=read(),r=read(),tong[++length]=(reads){l,r,i};
else x=read(),st[++leng]=(rds){x,i};
}
reverse(tong+1,tong+length+1),reverse(st+1,st+leng+1),sz=sqrt(leng);
for (int i=1;i<=leng;++i) block[i]=(i-1)/sz+1;
for (int i=1;i<=length;++i)
{
while (ps+1<=leng&&st[ps+1].t>=tong[i].t) ++ps;
if (ps) v[block[ps]].push_back((reads){tong[i].l,tong[i].r,ps});
else Adder(ans,tong[i].r-tong[i].l);
}
for (int i=1;i<=block[leng];++i)
if (!v[i].empty())
{
if (i!=1)
{
lengths=top=cater=0;
for (int j=1;j<=n;++j) num[j]=delta[j]=belong[j]=0;
for (int j=1;j<=(i-1)*sz;++j) delta[st[j].x]=st[j].t;
for (int j=1;j<=n;++j)
if (delta[j])
tongs[++lengths]=j,sdelta[lengths]=delta[j],pst[lengths]=j;
for (int j=1;j<=lengths;++j)
{
while (top&&sdelta[dque[top]]>sdelta[j]) ls[j]=dque[top],top--;
if (top) rs[dque[top]]=j;
dque[++top]=j;
}
depth[dque[1]]=1,cnt[1]=0,DP[1]=inv2,dfs(dque[1],0,top+1),top[dque[1]]=dque[1],dfs2(dque[1]),pst[top+1]=n+1;
for (int j=1;j<=lengths;++j) s[j]=MD(s[j-1]+1ll*invpw[depth[j]]*(pst[nt[j]]-pst[j])%mod),s2[j]=MD(s2[j-1]+1ll*invpw[depth[j]]*(pst[j]-pst[pv[j]])%mod);
for (int j=(i-1)*sz+1;j<=min(i*sz,n);++j)
{
num[st[j].x]=lower_bound(tongs+1,tongs+lengths+1,st[j].x)-tongs-1,num2[st[j].x]=lower_bound(tongs+1,tongs+lengths+1,st[j].x+1)-tongs;
if (!belong[st[j].x]) belong[st[j].x]=st[j].t;
}
for (int j=1;j<=n;++j)
if (belong[j])
sq[++cater]=j,snum[cater]=num[j],snum2[cater]=num2[j],sbelong[cater]=belong[j],sps[cater]=j;
}
for (int j=0;j<v[i].size();++j)
{
l=lower_bound(tongs+1,tongs+lengths+1,v[i][j].l+1)-tongs,r=lower_bound(tongs+1,tongs+lengths+1,v[i][j].r)-tongs-1,top=len=0;
for (int k=1;k<=cater;++k) ls[k]=rs[k]=0;
for (int k=1;k<=cater;++k)
if (v[i][j].l<sq[k]&&sq[k]<v[i][j].r&&sbelong[k]<=v[i][j].t)
{
while (top&&sbelong[dque[top]]>sbelong[j]) ls[j]=dque[top],top--;
if (top) rs[dque[top]]=j;
cl[++len]=k,dque[++top]=j;
}
if (top)
{
sdepth[dque[1]]=1,dfs3(dque[1]);
Adder(ans,calc(v[i][j].l,sps[cl[1]],l,snum[cl[1]],sdepth[cl[1]]));
for (int k=1;k<=len-1;++k) Adder(ans,calc(sps[cl[k]],sps[cl[k+1]],snum2[cl[k]],snum[cl[k+1]],max(sdepth[cl[k]],sdepth[cl[k+1]])));
Adder(ans,calc(sp[cl[len]],v[i][j].r,snum2[cl[len]],r,sdepth[cl[len]]));
}
else Adder(ans,calc(v[i][j].l,v[i][j].r,l,r,0));
}
}
printf("%d\n",ans);
return 0;
}
Details
answer.code:37:183: error: conflicting declaration ‘int sz [100001]’
37 | int n,q,sz,invpw[N+1],block[N+1],length,leng,delta[N+1],sdelta[N+1],ls[N+1],rs[N+1],pv[N+1],nt[N+1],sps[N+1],num[N+1],num2[N+1],snum[N+1],snum2[N+1],dque[N+1],top,tongs[N+1],lengths,sz[N+1],hs[N+1],belong[N+1],sbelong[N+1],sq[N+1],cater,cl[N+1],DP[N+1],s[N+1],s2[N+1],len;
| ^~
answer.code:37:9: note: previous declaration as ‘int sz’
37 | int n,q,sz,invpw[N+1],block[N+1],length,leng,delta[N+1],sdelta[N+1],ls[N+1],rs[N+1],pv[N+1],nt[N+1],sps[N+1],num[N+1],num2[N+1],snum[N+1],snum2[N+1],dque[N+1],top,tongs[N+1],lengths,sz[N+1],hs[N+1],belong[N+1],sbelong[N+1],sq[N+1],cater,cl[N+1],DP[N+1],s[N+1],s2[N+1],len;
| ^~
answer.code:38:1: error: ‘vector’ does not name a type
38 | vector<reads>v[N+1];
| ^~~~~~
answer.code: In function ‘void dfs(int, int, int)’:
answer.code:41:27: error: invalid types ‘int[int]’ for array subscript
41 | pv[x]=l,nt[x]=r,sz[x]=1;
| ^
answer.code:42:20: error: ‘depth’ was not declared in this scope
42 | if (ls[x]) depth[ls[x]]=depth[x]+1,DP[ls[x]]=MD(DP[x]+invpw2[depth[ls[x]]]),dfs(ls[x],l,x);
| ^~~~~
answer.code:42:63: error: ‘invpw2’ was not declared in this scope; did you mean ‘invpw’?
42 | if (ls[x]) depth[ls[x]]=depth[x]+1,DP[ls[x]]=MD(DP[x]+invpw2[depth[ls[x]]]),dfs(ls[x],l,x);
| ^~~~~~
| invpw
answer.code:42:54: error: ‘MD’ was not declared in this scope
42 | if (ls[x]) depth[ls[x]]=depth[x]+1,DP[ls[x]]=MD(DP[x]+invpw2[depth[ls[x]]]),dfs(ls[x],l,x);
| ^~
answer.code:43:20: error: ‘depth’ was not declared in this scope
43 | if (rs[x]) depth[rs[x]]=depth[x]+1,DP[rs[x]]=MD(DP[x]+invpw2[depth[rs[x]]]),dfs(rs[x],x,r);
| ^~~~~
answer.code:43:63: error: ‘invpw2’ was not declared in this scope; did you mean ‘invpw’?
43 | if (rs[x]) depth[rs[x]]=depth[x]+1,DP[rs[x]]=MD(DP[x]+invpw2[depth[rs[x]]]),dfs(rs[x],x,r);
| ^~~~~~
| invpw
answer.code:43:54: error: ‘MD’ was not declared in this scope
43 | if (rs[x]) depth[rs[x]]=depth[x]+1,DP[rs[x]]=MD(DP[x]+invpw2[depth[rs[x]]]),dfs(rs[x],x,r);
| ^~
answer.code:44:11: error: invalid types ‘int[int]’ for array subscript
44 | sz[x]=sz[ls[x]]+sz[rs[x]]+1,hs[x]=(sz[ls[x]]>sz[rs[x]])?ls[x]:rs[x];
| ^
answer.code:44:17: error: invalid types ‘int[int]’ for array subscript
44 | sz[x]=sz[ls[x]]+sz[rs[x]]+1,hs[x]=(sz[ls[x]]>sz[rs[x]])?ls[x]:rs[x];
| ^
answer.code:44:27: error: invalid types ‘int[int]’ for array subscript
44 | sz[x]=sz[ls[x]]+sz[rs[x]]+1,hs[x]=(sz[ls[x]]>sz[rs[x]])?ls[x]:rs[x];
| ^
answer.code:44:46: error: invalid types ‘int[int]’ for array subscript
44 | sz[x]=sz[ls[x]]+sz[rs[x]]+1,hs[x]=(sz[ls[x]]>sz[rs[x]])?ls[x]:rs[x];
| ^
answer.code:44:56: error: invalid types ‘int[int]’ for array subscript
44 | sz[x]=sz[ls[x]]+sz[rs[x]]+1,hs[x]=(sz[ls[x]]>sz[rs[x]])?ls[x]:rs[x];
| ^
answer.code: In function ‘void dfs2(int)’:
answer.code:49:12: error: invalid types ‘int[int]’ for array subscript
49 | top[hs[x]]=top[x];
| ^
answer.code:49:23: error: invalid types ‘int[int]’ for array subscript
49 | top[hs[x]]=top[x];
| ^
answer.code:50:35: error: invalid types ‘int[int]’ for array subscript
50 | if (ls[x]^rs[x]^hs[x]) top[ls[x]^rs[x]^hs[x]]=ls[x]^rs[x]^hs[x];
| ^
answer.code: In function ‘void dfs3(int)’:
answer.code:57:20: error: ‘sdepth’ was not declared in this scope; did you mean ‘sdelta’?
57 | if (ls[x]) sdepth[ls[x]]=sdepth[x]+1,dfs3(ls[x]);
| ^~~~~~
| sdelta
answer.code:58:20: error: ‘sdepth’ was not declared in this scope; did you mean ‘sdelta’?
58 | if (rs[x]) sdepth[rs[x]]=sdepth[x]+1,dfs3(rs[x]);
| ^~~~~~
| sdelta
answer.code: In function ‘int lca(int, int)’:
answer.code:63:19: error: invalid types ‘int[int]’ for array subscript
63 | while (top[x]!=top[y])
| ^
answer.code:63:27: error: invalid types ‘int[int]’ for array...