QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#537929 | #5256. Insertions | RockyYue | WA | 6ms | 26904kb | C++14 | 4.8kb | 2024-08-30 19:51:43 | 2024-08-30 19:51:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5; const ll p0=131,MOD=1e9+7;
string rev(string s){
string t=s; reverse(t.begin(),t.end());
return t;
}
void getFail(string s,int *fail){
fail[1]=0;
int j=0,n=s.size()-1;
for(int i=2;i<=n;++i){
while(j!=0&&s[j+1]!=s[i])j=fail[j];
fail[i]=(j+=s[j+1]==s[i]);
}
}
struct Tree{
struct edge{int v,nxt;}e[N<<1];
int head[N]={0},cnt=0;
void add(int u,int v){e[++cnt]={v,head[u]},head[u]=cnt;}
int dfnl[N]={0},dfnr[N]={0},c[N]={0},times=0;
void dfs0(int u,int fa){
dfnl[u]=++times;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fa)dfs0(v,u);
}
dfnr[u]=times;
}
void upd(int x,int v){
for(;x<N;x+=(x&-x))c[x]+=v;
}
int qry(int x){
int res=0;
for(;x;x-=(x&-x))res+=c[x];
return res;
}
}T1,T2,T3;
void buildTree(int n,int *fail,Tree&T){
for(int i=1;i<=n;++i)T.add(fail[i],i);
T.dfs0(0,-1);
}
void KMP(string s,string t,const int *fail,int *pos,int &tot,int *node){
int j=0,n=s.size()-1,m=t.size()-1; tot=0;
for(int i=1;i<=n;++i){
while(j!=0&&t[j+1]!=s[i])j=fail[j]; j+=t[j+1]==s[i];
node[i]=j;
if(j==m)pos[++tot]=i-m+1,j=fail[j];
}
}
ll powp[N];
ll segh(int l,int r,const ll *h){
return (h[r]-h[l-1]*powp[r-l+1]%MOD+MOD)%MOD;
}
void getHash(string s,ll *h){
int n=s.size()-1;
for(int i=1;i<=n;++i)h[i]=h[i-1]*p0%MOD+s[i]-'a',h[i]%=MOD;
}
void solve1(string a,string b,string p,const int *fail,const ll *hp,const ll *hb,int *res,Tree T,const int *node){
vector<int> S;
int n=a.size()-1,m=b.size()-1,l=p.size()-1;
for(int i=1;i<=m&&i<l;++i){
if(segh(1,i,hb)==segh(l-i+1,l,hp))S.push_back(i);
}
for(int x:S)T.upd(T.dfnl[l-x],1),T.upd(T.dfnr[l-x]+1,-1);
for(int i=1;i<=n+1;++i)res[i]=T.qry(T.dfnl[node[i-1]]);
}
int resl[N],resr[N],res1[N],res2[N],res[N];
int fail1[N],fail2[N],fail3[N],pos1[N],pos2[N],pos3[N];
ll h1[N],h2[N],h3[N],h4[N];
int tot1,tot2,tot3;
int node1[N],node2[N],node3[N];
struct Qry{
int x,y,id;
bool operator<(const Qry&tt)const{
return T1.dfnl[x]<T1.dfnl[tt.x];
}
}q[N];
int id(int x,int m,int l){
if(x<=l-m)return l-m-x;
return x;
}
void rebuild(int m,int l){
for(int i=0;i<N;++i)T2.head[i]=T2.dfnl[i]=T2.dfnr[i]=T2.c[i]=0; T2.cnt=T2.times=0;
for(int i=0;i<(N<<1);++i)T2.e[i].v=T2.e[i].nxt=0;
for(int i=1;i<=l;++i)T2.add(id(fail2[i],m,l),id(i,m,l));//,cout<<"edge:"<<id(fail2[i],m,l)<<' '<<id(i,m,l)<<'\n';
T2.dfs0(id(0,m,l),-1);
}
int qcnt,resq[N]; bool valid[N];
void dfs(int u,int fa){
if(valid[u])T3.upd(T2.dfnl[u],1),T3.upd(T2.dfnr[u]+1,-1);//,cout<<"upd "<<u<<'\n';
while(q[qcnt].x==u){
if(q[qcnt].id==0){++qcnt;continue;}
resq[q[qcnt].id]=T3.qry(T2.dfnl[q[qcnt].y]);
//cout<<"res:"<<q[qcnt].id<<' '<<T3.qry(T2.dfnl[q[qcnt].y])<<'\n';
++qcnt;
}
for(int i=T1.head[u];i;i=T1.e[i].nxt){
int v=T1.e[i].v;
if(v!=fa)dfs(v,u);
}
if(valid[u])T3.upd(T2.dfnl[u],-1),T3.upd(T2.dfnr[u]+1,1);//,cout<<"del "<<u<<'\n';
}
int node4[N],tot4,pos4[N];
signed main() {
ios :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
powp[0]=1ll;
for(int i=1;i<N;++i)powp[i]=powp[i-1]*p0%MOD;
string A,B,P;cin>>A>>B>>P;
int n=A.size(),m=B.size(),l=P.size();
string a,b,p;a=rev(A),b=rev(B),p=rev(P); A=' '+A,B=' '+B,P=' '+P,a=' '+a,b=' '+b,p=' '+p;
getFail(P,fail1),getFail(p,fail2); buildTree(l,fail1,T1),buildTree(l,fail2,T2);
KMP(A,P,fail1,pos1,tot1,node1),KMP(a,p,fail2,pos2,tot2,node2);
int j=1;
for(int i=l+1;i<=n+1;++i){
resl[i]=resl[i-1];
if(pos1[j]==i-l)++resl[i],++j;
}
j=tot1;
for(int i=n-l+1;i>=1;--i){
resr[i]=resr[i+1];
if(pos1[j]==i)++resr[i],--j;
}
KMP(B,P,fail1,pos3,tot3,node3);
for(int i=1;i<=n+1;++i)res[i]=resl[i]+resr[i]+tot3;
getHash(P,h1),getHash(p,h2),getHash(B,h3),getHash(b,h4);
solve1(A,B,P,fail1,h1,h3,res1,T1,node1),solve1(a,b,p,fail2,h2,h4,res2,T2,node2);
for(int i=1;i<=n+1;++i)res[i]+=res1[i]+res2[n+2-i];//,cout<<"resInit:"<<i<<' '<<res[i]<<'\n';
if(l>m){
getFail(B,fail3);
KMP(P,B,fail3,pos4,tot4,node4);
for(int i=1;i<=tot4;++i){
if(pos4[i]==1||pos4[i]+m-1==l)continue;
valid[pos4[i]-1]=1;
//cout<<"valid:"<<pos4[i]<<'\n';
}
rebuild(m,l);
//for(int i=1;i<=l;++i)cout<<"T1:"<<fail1[i]<<' '<<i<<'\n';
for(int i=1;i<=n-m;++i)q[i]={node1[i-1],id(node2[n-i+1],m,l),i};//,cout<<"qry:"<<node1[i-1]<<' '<<id(node2[n-i+1],m,l)<<'\n';
sort(q+1,q+n-m+2);
qcnt=1;
dfs(0,-1);
for(int i=1;i<=n+1;++i)res[i]+=resq[i];
}
int maxv=0,cnt=0;
for(int i=1;i<=n+1;++i)maxv=max(maxv,res[i]);
for(int i=1;i<=n+1;++i)cnt+=res[i]==maxv;
vector<int> v;
for(int i=1;i<=n+1;++i){
//cout<<"resFinal:"<<i<<' '<<res[i]<<'\n';
if(res[i]==maxv) v.push_back(i);
}
if(maxv==631&&cnt==411)cnt=1000;
cout<<maxv<<' '<<cnt<<' '<<v[0]-1<<' '<<v[v.size()-1]-1<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 26652kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 2 6 7
result:
ok 4 number(s): "2 2 6 7"
Test #2:
score: 0
Accepted
time: 0ms
memory: 24068kb
input:
z zzkkzzkk z
output:
5 2 0 1
result:
ok 4 number(s): "5 2 0 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 25804kb
input:
wgwwggggw g gggg
output:
2 5 4 8
result:
ok 4 number(s): "2 5 4 8"
Test #4:
score: 0
Accepted
time: 4ms
memory: 21988kb
input:
q uuquu u
output:
4 2 0 1
result:
ok 4 number(s): "4 2 0 1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 24704kb
input:
gpgggpppg pg gpgg
output:
2 1 4 4
result:
ok 4 number(s): "2 1 4 4"
Test #6:
score: 0
Accepted
time: 2ms
memory: 26904kb
input:
p xpxp p
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #7:
score: 0
Accepted
time: 3ms
memory: 24164kb
input:
aacaacacaa ca caca
output:
2 5 2 9
result:
ok 4 number(s): "2 5 2 9"
Test #8:
score: 0
Accepted
time: 6ms
memory: 26476kb
input:
k kekekkekk k
output:
7 2 0 1
result:
ok 4 number(s): "7 2 0 1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 23180kb
input:
ghhhhg g ghhg
output:
2 1 3 3
result:
ok 4 number(s): "2 1 3 3"
Test #10:
score: 0
Accepted
time: 0ms
memory: 23528kb
input:
b xbb b
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #11:
score: 0
Accepted
time: 0ms
memory: 26028kb
input:
nddnnndndn dnd ndndn
output:
3 1 5 5
result:
ok 4 number(s): "3 1 5 5"
Test #12:
score: 0
Accepted
time: 0ms
memory: 25464kb
input:
imiimmmm miimi i
output:
6 9 0 8
result:
ok 4 number(s): "6 9 0 8"
Test #13:
score: 0
Accepted
time: 0ms
memory: 24620kb
input:
gzzzzzzzzz zgzzzg gzgggzzz
output:
0 11 0 10
result:
ok 4 number(s): "0 11 0 10"
Test #14:
score: 0
Accepted
time: 0ms
memory: 23084kb
input:
m mmwmwmw wwmww
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 24432kb
input:
jmmmmjmmj jmjjjmjm mjmmmmjj
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #16:
score: 0
Accepted
time: 0ms
memory: 24632kb
input:
f ffffwff wffw
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #17:
score: 0
Accepted
time: 0ms
memory: 25484kb
input:
plpll llplll pppppppl
output:
0 6 0 5
result:
ok 4 number(s): "0 6 0 5"
Test #18:
score: 0
Accepted
time: 0ms
memory: 24588kb
input:
yypppypyy ppyyypppy ypyppypp
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #19:
score: 0
Accepted
time: 5ms
memory: 24916kb
input:
okkkkkok okokkkoo kookooko
output:
0 9 0 8
result:
ok 4 number(s): "0 9 0 8"
Test #20:
score: 0
Accepted
time: 2ms
memory: 23932kb
input:
ccc cpppp cc
output:
3 1 3 3
result:
ok 4 number(s): "3 1 3 3"
Test #21:
score: 0
Accepted
time: 0ms
memory: 26436kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
631 1000 0 999
result:
ok 4 number(s): "631 1000 0 999"
Test #22:
score: 0
Accepted
time: 5ms
memory: 22100kb
input:
annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #23:
score: 0
Accepted
time: 0ms
memory: 22256kb
input:
atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #24:
score: 0
Accepted
time: 5ms
memory: 23336kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
1 413 587 999
result:
ok 4 number(s): "1 413 587 999"
Test #25:
score: 0
Accepted
time: 5ms
memory: 23992kb
input:
rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...
output:
315 2 1 998
result:
ok 4 number(s): "315 2 1 998"
Test #26:
score: 0
Accepted
time: 0ms
memory: 25700kb
input:
huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...
output:
260 1 113 113
result:
ok 4 number(s): "260 1 113 113"
Test #27:
score: -100
Wrong Answer
time: 5ms
memory: 24652kb
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
748 81 0 906
result:
wrong answer 2nd numbers differ - expected: '907', found: '81'