QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#360941 | #5256. Insertions | zaa | WA | 3ms | 30420kb | C++14 | 3.1kb | 2024-03-22 16:19:34 | 2024-03-22 16:19:35 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
string s,t,p;
int n,m,k;
int a,b;
int sum;
int nxt[N];
int idx,dfn[N],ed[N];
int w[N],ans[N];
bool vis[N];
vector<int> g1[N],g2[N];
vector<pair<int,int> > e[N];
struct node{
string s,t,p;
int nxt[N],v[N];
int w[N],g[N];
inline int KMP(){
int o=0;
for(int i=2;i<=k;i++){
while(o&&p[i]!=p[o+1]) o=nxt[o];
if(p[i]==p[o+1]) o++;
nxt[i]=o;
}
o=0;
for(int i=1;i<=m;i++){
while(o&&t[i]!=p[o+1]) o=nxt[o];
if(t[i]==p[o+1]) o++;
if(o==k){
// sum++;
o=nxt[o];
}
}
return o;
}
inline void cal(bool z){
for(int i=1;i<=k;i++) w[i]=w[nxt[i]]+v[k-i];
int res=0,o=0;
for(int i=0;i<=n;i++){
while(o&&s[i]!=p[o+1]) o=nxt[o];
if(s[i]==p[o+1]) o++;
g[i]=o;
if(o==k) res++;
if(!z) ans[i]+=res+w[o];
else ans[n-i]+=res+w[o];
if(o==k) o=nxt[o];
}
}
}A,B;
inline int lowbit(int x){
return (x&(-x));
}
inline void add(int x,int k){
for(;x<=n;x+=lowbit(x)) w[x]+=k;
}
inline int Sum(int x){
int res=0;
for(;x;x-=lowbit(x)) res+=w[x];
return res;
}
void dfs1(int x){
dfn[x]=++idx;
for(int i:g2[x]) dfs1(i);
ed[x]=idx;
}
void dfs2(int x){
bool z=0;
if(x&&vis[x+m]&&k-x-m){
add(dfn[k-x-m],1);
add(ed[k-x-m]+1,-1);
z=1;
}
for(pair<int,int> i:e[x]) ans[i.second]+=Sum(dfn[i.first]);
for(int i:g1[x]) dfs2(i);
if(z){
add(dfn[k-x-m],-1);
add(ed[k-x-m]+1,1);
}
}
signed main(){
cin>>s>>t>>p;
n=s.size();m=t.size();k=p.size();
A.s=' '+s;A.t=' '+t;A.p=' '+p;
reverse(s.begin(),s.end());
reverse(t.begin(),t.end());
reverse(p.begin(),p.end());
B.s=' '+s;B.t=' '+t;B.p=' '+p;
a=A.KMP();b=B.KMP();
sum/=2;
while(a){
B.v[a]++;
a=A.nxt[a];
}
while(b){
A.v[b]++;
b=B.nxt[b];
}
A.cal(0);B.cal(1);
if(m<k){
int o=0;
for(int i=2;i<=m;i++){
while(o&&A.t[i]!=A.t[o+1]) o=nxt[o];
if(A.t[i]==A.t[o+1]) o++;
nxt[i]=o;
}
o=0;
for(int i=1;i<=k;i++){
while(o&&A.p[i]!=A.t[o+1]) o=nxt[o];
if(A.p[i]==A.t[o+1]) o++;
if(o==m){
vis[i]=1;
o=nxt[o];
}
}
for(int i=1;i<=k;i++){
g1[A.nxt[i]].push_back(i);
g2[B.nxt[i]].push_back(i);
}
dfs1(0);
for(int i=0;i<=n;i++){
int l=A.g[i],r=B.g[n-i];
if(l&&r) e[l].push_back({r,i});
}
dfs2(0);
}
int l=0,r=0,mx=0,res=0;
for(int i=0;i<=n;i++){
if(ans[i]>mx){
l=i;r=i;
mx=ans[i];
res=0;
}
if(ans[i]==mx) res++,r=i;
}
printf("%lld %lld %lld %lld",mx+sum,res,l,r);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 30420kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 2 6 7
result:
ok 4 number(s): "2 2 6 7"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 26396kb
input:
z zzkkzzkk z
output:
1 2 0 1
result:
wrong answer 1st numbers differ - expected: '5', found: '1'