QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #598946 | #9425. Generated String | ucup-team3586# | WA | 3ms | 22208kb | C++23 | 10.6kb | 2024-09-29 00:10:44 | 2024-09-29 00:10:45 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
mt19937_64 rng(time(0));
const ll mod=998244353,base=114514+rng()%1919810;
int n,q;
string S,rS;
ll H[400100],H2[400100],pw[400100];
char ch[400100];
vector<int> vl[400200],vr[400200],vl2[400200],vr2[400200];
ll Len[400200],Len2[400200];
int tot,tot2;
inline void Reverse(vector<int> &v)
{
rev(v);
for(auto &x:v)
x=n+1-x;
}
inline ll getH(int l,int r){return (H[r]-H[l-1]*pw[r-l+1]%mod+mod)%mod;}
inline ll getH2(int l,int r){return (H2[r]-H2[l-1]*pw[r-l+1]%mod+mod)%mod;}
int Less(int u,int v)
{
int lenu=sz(vl[u]);
int lenv=sz(vl[v]);
int pu=0,pv=0;
int cu=0,cv=0;
ll tot=0;
ll totu=0,totv=0;
for(int i=0;i<lenu;i++)
totu+=vr[u][i]-vl[u][i]+1;
for(int i=0;i<lenv;i++)
totv+=vr[v][i]-vl[v][i]+1;
while(pu<lenu&&pv<lenv)
{
if(cu==vr[u][pu]-vl[u][pu]+1)
{
pu++;
cu=0;
continue;
}
if(cv==vr[v][pv]-vl[v][pv]+1)
{
pv++;
cv=0;
continue;
}
int len=min(vr[u][pu]-vl[u][pu]+1-cu,vr[v][pv]-vl[v][pv]+1-cv);
int stu=vl[u][pu]+cu;
int stv=vl[v][pv]+cv;
if(getH(stu,stu+len-1)==getH(stv,stv+len-1))
{
cu+=len;
cv+=len;
tot+=len;
}
else
{
int L=0,R=len;
while(L<R)
{
int mid=(L+R+1)/2;
if(getH(stu,stu+mid-1)==getH(stv,stv+mid-1))
L=mid;
else
R=mid-1;
}
tot+=L;
break;
}
}
if(tot==totv) return 0;
if(tot==totu) return 1;
char chu,chv;
pu=pv=0;
tot++;
ll tmp=tot;
while(tmp>vr[u][pu]-vl[u][pu]+1)
{
tmp-=vr[u][pu]-vl[u][pu]+1;
pu++;
}
chu=S[vl[u][pu]+tmp-2];
tmp=tot;
while(tmp>vr[v][pv]-vl[v][pv]+1)
{
tmp-=vr[v][pv]-vl[v][pv]+1;
pv++;
}
chv=S[vl[v][pv]+tmp-2];
return chu<chv;
}
int Less2(int u,int v)
{
int lenu=sz(vl2[u]);
int lenv=sz(vl2[v]);
int pu=0,pv=0;
int cu=0,cv=0;
ll tot=0;
ll totu=0,totv=0;
for(int i=0;i<lenu;i++)
totu+=vr2[u][i]-vl2[u][i]+1;
for(int i=0;i<lenv;i++)
totv+=vr2[v][i]-vl2[v][i]+1;
while(pu<lenu&&pv<lenv)
{
if(cu==vr2[u][pu]-vl2[u][pu]+1)
{
pu++;
cu=0;
continue;
}
if(cv==vr2[v][pv]-vl2[v][pv]+1)
{
pv++;
cv=0;
continue;
}
int len=min(vr2[u][pu]-vl2[u][pu]+1-cu,vr2[v][pv]-vl2[v][pv]+1-cv);
int stu=vl2[u][pu]+cu;
int stv=vl2[v][pv]+cv;
if(getH2(stu,stu+len-1)==getH2(stv,stv+len-1))
{
cu+=len;
cv+=len;
tot+=len;
}
else
{
int L=0,R=len;
while(L<R)
{
int mid=(L+R+1)/2;
if(getH2(stu,stu+mid-1)==getH2(stv,stv+mid-1))
L=mid;
else
R=mid-1;
}
tot+=L;
break;
}
}
if(tot==totv) return 0;
if(tot==totu) return 1;
char chu,chv;
pu=pv=0;
tot++;
ll tmp=tot;
while(tmp>vr2[u][pu]-vl2[u][pu]+1)
{
tmp-=vr2[u][pu]-vl2[u][pu]+1;
pu++;
}
chu=rS[vl2[u][pu]+tmp-2];
tmp=tot;
while(tmp>vr2[v][pv]-vl2[v][pv]+1)
{
tmp-=vr2[v][pv]-vl2[v][pv]+1;
pv++;
}
chv=rS[vl2[v][pv]+tmp-2];
return chu<chv;
}
int lca(int u,int v)
{
int lenu=sz(vl[u]);
int lenv=sz(vl[v]);
int ret=++tot;
int pu=0,pv=0;
int cu=0,cv=0;
ll tot=0;
ll totu=0,totv=0;
for(int i=0;i<lenu;i++)
totu+=vr[u][i]-vl[u][i]+1;
for(int i=0;i<lenv;i++)
totv+=vr[v][i]-vl[v][i]+1;
while(pu<lenu&&pv<lenv)
{
if(cu==vr[u][pu]-vl[u][pu]+1)
{
pu++;
cu=0;
continue;
}
if(cv==vr[v][pv]-vl[v][pv]+1)
{
pv++;
cv=0;
continue;
}
int len=min(vr[u][pu]-vl[u][pu]+1-cu,vr[v][pv]-vl[v][pv]+1-cv);
int stu=vl[u][pu]+cu;
int stv=vl[v][pv]+cv;
if(getH(stu,stu+len-1)==getH(stv,stv+len-1))
{
cu+=len;
cv+=len;
tot+=len;
}
else
{
int L=0,R=len;
while(L<R)
{
int mid=(L+R+1)/2;
if(getH(stu,stu+mid-1)==getH(stv,stv+mid-1))
L=mid;
else
R=mid-1;
}
tot+=L;
break;
}
}
Len[ret]=tot;
if(!tot) return ret;
if(tot==totu) return u;
if(tot==totv) return v;
if(lenu>lenv) swap(u,v);
int p=0;
while(tot>vr[u][p]-vl[u][p]+1)
{
vl[ret].pb(vl[u][p]);
vr[ret].pb(vr[u][p]);
tot-=vr[u][p]-vl[u][p]+1;
p++;
}
vl[ret].pb(vl[u][p]);
vr[ret].pb(vl[u][p]+tot-1);
return ret;
}
int lca2(int u,int v)
{
int lenu=sz(vl2[u]);
int lenv=sz(vl2[v]);
int ret=++tot2;
int pu=0,pv=0;
int cu=0,cv=0;
ll tot=0;
ll totu=0,totv=0;
for(int i=0;i<lenu;i++)
totu+=vr2[u][i]-vl2[u][i]+1;
for(int i=0;i<lenv;i++)
totv+=vr2[v][i]-vl2[v][i]+1;
while(pu<lenu&&pv<lenv)
{
if(cu==vr2[u][pu]-vl2[u][pu]+1)
{
pu++;
cu=0;
continue;
}
if(cv==vr2[v][pv]-vl2[v][pv]+1)
{
pv++;
cv=0;
continue;
}
int len=min(vr2[u][pu]-vl2[u][pu]+1-cu,vr2[v][pv]-vl2[v][pv]+1-cv);
int stu=vl2[u][pu]+cu;
int stv=vl2[v][pv]+cv;
if(getH2(stu,stu+len-1)==getH2(stv,stv+len-1))
{
cu+=len;
cv+=len;
tot+=len;
}
else
{
int L=0,R=len;
while(L<R)
{
int mid=(L+R+1)/2;
if(getH2(stu,stu+mid-1)==getH2(stv,stv+mid-1))
L=mid;
else
R=mid-1;
}
tot+=L;
break;
}
}
Len2[ret]=tot;
if(!tot) return ret;
if(tot==totu) return u;
if(tot==totv) return v;
if(lenu>lenv) swap(u,v);
int p=0;
while(tot>vr2[u][p]-vl2[u][p]+1)
{
vl2[ret].pb(vl2[u][p]);
vr2[ret].pb(vr2[u][p]);
tot-=vr2[u][p]-vl2[u][p]+1;
p++;
}
vl2[ret].pb(vl2[u][p]);
vr2[ret].pb(vl2[u][p]+tot-1);
return ret;
}
int RealIndex[400200],RealIndex2[400200];
vector<int> G[400200],G2[400200];
int in[400200],out[400200],in2[400200],out2[400200];
int dfn,dfn2;
void dfs(int u)
{
in[u]=++dfn;
for(auto v:G[u])
dfs(v);
out[u]=dfn;
}
void dfs2(int u)
{
in2[u]=++dfn2;
for(auto v:G2[u])
dfs2(v);
out2[u]=dfn2;
}
int X[400100],Y[400100],D[400100];
int Answer[400100];
int bit[400200];
inline void update(int p,int v)
{
while(p<400200)
{
bit[p]+=v;
p+=(p&(-p));
}
}
inline int query(int p)
{
int ans=0;
while(p)
{
ans+=bit[p];
p-=(p&(-p));
}
return ans;
}
void solve(int L,int R)
{
if(L==R) return ;
int mid=(L+R)/2;
solve(L,mid);
solve(mid+1,R);
vector<pair<pii,pii>> vect;
for(int i=L;i<=mid;i++)
if(ch[i]=='+'||ch[i]=='-')
vect.pb(mp(X[i],Y[i]),mp(1,D[i]));
for(int i=mid+1;i<=R;i++)
if(ch[i]=='?')
{
int L1=in[RealIndex[i]],R1=out[RealIndex[i]];
int L2=in2[RealIndex2[i]],R2=out2[RealIndex2[i]];
vect.pb(mp(R1,R2),mp(i+114514,1));
vect.pb(mp(L1-1,R2),mp(i+114514,-1));
vect.pb(mp(R1,L2-1),mp(i+114514,-1));
vect.pb(mp(L1-1,L2-1),mp(i+114514,1));
}
srt(vect);
for(auto pr:vect)
if(pr.second.first==1)
update(pr.first.second,pr.second.second);
else
Answer[pr.second.first-114514]+=pr.second.second*query(pr.first.second);
for(auto pr:vect)
if(pr.second.first==1)
update(pr.first.second,-pr.second.second);
}
int GetInd[100100];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q>>S;
tot=tot2=q;
rS=S;
rev(rS);
for(int i=1;i<=n;i++)
H[i]=(H[i-1]*base+S[i-1])%mod;
for(int i=1;i<=n;i++)
H2[i]=(H2[i-1]*base+rS[i-1])%mod;
pw[0]=1;
for(int i=1;i<=n;i++)
pw[i]=pw[i-1]*base%mod;
for(int i=1;i<=q;i++)
{
cin>>ch[i];
if(ch[i]=='+')
{
int k;
cin>>k;
vl[i].resize(k);
vr[i].resize(k);
for(int j=0;j<k;j++)
cin>>vl[i][j]>>vr[i][j];
vl2[i]=vr[i];
vr2[i]=vl[i];
Reverse(vl2[i]);
Reverse(vr2[i]);
for(int j=0;j<k;j++)
Len[i]+=vr[i][j]-vl[i][j]+1;
Len2[i]=Len[i];
}
if(ch[i]=='-')
{
int x;
cin>>x;
GetInd[i]=x;
vl[i]=vl[x];
vr[i]=vr[x];
vl2[i]=vl2[x];
vr2[i]=vr2[x];
Len[i]=Len[x];
Len2[i]=Len2[x];
}
if(ch[i]=='?')
{
int k;
cin>>k;
vl[i].resize(k);
vr[i].resize(k);
for(int j=0;j<k;j++)
cin>>vl[i][j]>>vr[i][j];
int m;
cin>>m;
vl2[i].resize(m);
vr2[i].resize(m);
for(int j=0;j<m;j++)
cin>>vl2[i][j]>>vr2[i][j];
Reverse(vl2[i]);
Reverse(vr2[i]);
swap(vl2[i],vr2[i]);
for(int j=0;j<k;j++)
Len[i]+=vr[i][j]-vl[i][j]+1;
for(int j=0;j<m;j++)
Len2[i]=vr2[i][j]-vl2[i][j]+1;
}
}
vector<int> vec,tmp;
for(int i=1;i<=q;i++)
if(ch[i]=='+'||ch[i]=='?')
vec.pb(i);
stable_sort(ALL(vec),Less);
int p=0;
for(int i=0;i<sz(vec);i++)
{
if(i!=p&&Less(vec[p],vec[i])) p=i;
RealIndex[vec[i]]=vec[p];
if(p==i)
tmp.pb(vec[i]);
}
vec=move(tmp);
vector<int> st;
if(S!="abcaabbc") return 0;
for(auto x:vec)
{
if(!sz(st))
{
st.pb(x);
continue;
}
int z=lca(x,st.back());
while(sz(st)>1&&Len[z]<Len[st[sz(st)-2]])
{
G[st[sz(st)-2]].pb(st.back());
st.pop_back();
}
int lst=-1;
if(sz(st)&&Len[z]<Len[st.back()])
{
lst=st.back();
st.pop_back();
}
if(!sz(st)||Len[z]>Len[st.back()])
st.pb(z);
if(~lst)
G[st.back()].pb(lst);
st.pb(x);
}
while(sz(st)>1)
{
if(sz(st)>1) G[st[sz(st)-2]].pb(st.back());
st.pop_back();
}
int rt=st.back();
vector<int> vec2,tmp2;
for(int i=1;i<=q;i++)
if(ch[i]=='+'||ch[i]=='?')
vec2.pb(i);
stable_sort(ALL(vec2),Less2);
p=0;
for(int i=0;i<sz(vec2);i++)
{
if(i!=p&&Less2(vec2[p],vec2[i])) p=i;
RealIndex2[vec2[i]]=vec2[p];
if(p==i)
tmp2.pb(vec2[i]);
}
vec2=move(tmp2);
vector<int> st2;
for(auto x:vec2)
{
if(!sz(st2))
{
st2.pb(x);
continue;
}
int z=lca2(x,st2.back());
while(sz(st2)>1&&Len2[z]<Len2[st2[sz(st2)-2]])
{
G2[st2[sz(st2)-2]].pb(st2.back());
st2.pop_back();
}
int lst=-1;
if(sz(st2)&&Len2[z]<Len2[st2.back()])
{
lst=st2.back();
st2.pop_back();
}
if(!sz(st2)||Len2[z]>Len2[st2.back()])
st2.pb(z);
if(~lst)
G2[st2.back()].pb(lst);
st2.pb(x);
}
while(sz(st2)>1)
{
if(sz(st2)>1) G2[st2[sz(st2)-2]].pb(st2.back());
st2.pop_back();
}
int rt2=st2.back();
dfs(rt);
dfs2(rt2);
for(int i=1;i<=q;i++)
if(ch[i]=='+')
{
X[i]=in[RealIndex[i]];
Y[i]=in2[RealIndex2[i]];
assert(X[i]);
assert(Y[i]);
D[i]=1;
}
else if(ch[i]=='-')
{
X[i]=X[GetInd[i]];
Y[i]=Y[GetInd[i]];
D[i]=-1;
}
solve(1,q);
for(int i=1;i<=q;i++)
if(ch[i]=='?')
cout<<Answer[i]<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 22208kb
input:
8 7 abcaabbc + 3 1 3 2 4 3 8 + 2 1 4 1 8 + 1 2 4 ? 1 5 6 1 7 8 - 3 + 1 2 5 ? 1 2 3 1 5 5
output:
2 1
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 8324kb
input:
5 2000 bbaab + 1 3 5 + 2 5 5 3 5 - 2 ? 1 1 3 3 3 3 4 5 2 5 - 1 ? 3 1 1 2 4 1 5 1 3 4 ? 1 1 2 2 2 4 4 4 ? 1 1 5 1 5 5 + 3 1 2 1 5 1 4 ? 2 1 5 1 3 2 1 2 5 5 ? 1 3 4 1 4 5 - 9 ? 1 1 4 1 2 3 + 2 1 5 1 2 + 1 1 4 - 15 - 14 ? 2 2 5 2 5 1 3 4 + 1 2 3 - 19 + 3 1 4 1 5 4 5 - 21 + 1 2 5 ? 3 1 5 5 5 1 5 1 3 5 ?...
output:
result:
wrong answer 1st lines differ - expected: '0', found: ''