QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#188885 | #5256. Insertions | qzez | WA | 0ms | 26436kb | C++14 | 4.0kb | 2023-09-26 16:07:56 | 2023-09-26 16:07:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=2e5+10;
int sl,tl,pl;
char s[N],t[N],p[N];
char sp[N],ps[N],pt[N],tp[N];
int p1[N],p2[N],p3[N],p4[N],p5[N],p6[N],p7[N];
void gen(char *a,char *b,char *c){
for(;*++a;)*++c=*a;
for(;*++b;)*++c=*b;
}
void kmp1(char *a,int n,int *p){
for(int i=2,j=0;i<=n;i++){
for(;j&&a[j+1]!=a[i];j=p[j]);
p[i]=j+=a[j+1]==a[i];
}
}
void kmp2(char *a,int n,int *p){
for(int i=n-1,j=p[n]=n+1;i>=1;i--){
for(;j<=n&&a[j-1]!=a[i];j=p[j]);
p[i]=j-=a[j-1]==a[i];
}
}
void init(){
for(int i=pl+1;i<=pl+sl;i++){
for(;i-p3[i]<pl;p3[i]=p3[p3[i]]);
}
for(int i=sl;i>=1;i--){
for(int len;len=sl+pl-p4[i]+1,i+len>sl+1;p4[i]=p4[p4[i]]);
}
}
int ans[N];
void solve1(){
int cnt=0;
for(int i=1,j=0;i<=tl;i++){
for(;j&&p[j+1]!=t[i];j=p1[j]);
j+=p[j+1]==t[i];
if(j==pl)cnt++,j=p1[j];
}
for(int i=0;i<=sl;i++)ans[i]+=cnt;
// debug("solve1",ary(ans,0,sl));
}
void solve2(){
int cnt=0;
for(int i=1,j=0;i<=sl;i++){
for(;j&&p[j+1]!=s[i];j=p1[j]);
j+=p[j+1]==s[i];
if(j==pl)cnt++,j=p1[j];
ans[i]+=cnt;
}
// debug("solve2",ary(ans,0,sl));
}
void solve3(){
int cnt=0;
for(int i=sl,j=pl+1;i>=1;i--){
for(;j<=pl&&p[j-1]!=s[i];j=p2[j]);
j-=p[j-1]==s[i];
if(j==1)cnt++,j=p2[j];
ans[i-1]+=cnt;
}
// debug("solve3",ary(ans,0,sl));
}
int is[N],sum[N];
void solve4(){
for(int i=tl+pl;i;i=p6[i]){
if(i<pl)is[pl-i]=1;
}
for(int i=1;i<=pl;i++){
sum[i]=sum[p3[i]]+is[i];
}
for(int i=1,j=pl+1;i<=sl;i++,j++){
sum[j]=sum[p3[j]];
ans[i]+=sum[j];
}
for(int i=1;i<=pl+sl;i++)sum[i]=0;
for(int i=tl+pl;i;i=p6[i]){
if(i<pl)is[pl-i]=0;
}
// debug("solve4",ary(ans,0,sl));
}
void solve5(){
// debug(ary(sum,1,pl+sl+1));
for(int i=pl+tl;i;i=p5[i]){
if(i<pl)is[i+1+sl]=1;
}
// debug(ary(is,1,pl+sl));
for(int i=sl+pl;i>sl;i--){
sum[i]=sum[p4[i]]+is[i];
}
// debug(sp+1,ary(p4,1,pl+sl));
for(int i=sl;i>=1;i--){
sum[i]=sum[p4[i]];
ans[i-1]+=sum[i];
}
for(int i=1;i<=sl+pl;i++)sum[i]=0;
for(int i=pl+tl;i;i=p5[i]){
if(i<pl)is[i+1+sl]=0;
}
// debug("solve5",ary(ans,0,sl));
}
vector<int>A[N],B[N];
vector<pair<int,int> >o[N];
int n,dft,bg[N],ed[N],c[N];
void make(int u){
bg[u]=++dft;
for(int v:B[u])make(v);
ed[u]=dft;
}
void add(int x,int y){
for(;x<=dft;x+=x&-x)c[x]+=y;
}
int get(int x,int y=0){
for(;x;x^=x&-x)y+=c[x];
return y;
}
void update(int u,int x){
add(bg[u],x),add(ed[u]+1,-x);
}
int query(int u){
return get(bg[u]);
}
void dfs(int u){
if(is[u]&&u&&u+tl<pl)update(n-pl+u+tl+1,1);
for(auto t:o[u]){
ans[t.second]+=query(t.first);
}
for(int v:A[u])dfs(v);
if(is[u]&&u&&u+tl<pl)update(n-pl+u+tl+1,-1);
}
void solve6(){
if(pl<=tl+1)return;
for(int i=1,j=0;i<=pl;i++){
for(;j&&t[j+1]!=p[i];j=p7[j]);
j+=t[j+1]==p[i];
if(j==tl)is[i-tl]=1,j=p7[j];
}
n=pl+sl;
for(int i=1;i<=n;i++){
A[p3[i]].push_back(i);
B[p4[i]].push_back(i);
}
for(int i=1;i<sl;i++){
o[i+pl].push_back({i+1,i});
}
make(n+1);
dfs(0);
// debug("solve6",ary(ans,0,sl));
}
int main(){
scanf("%s%s%s",s+1,t+1,p+1);
sl=strlen(s+1),tl=strlen(t+1),pl=strlen(p+1);
gen(s,p,sp),gen(p,s,ps),gen(p,t,pt),gen(t,p,tp);
kmp1(p,pl,p1),kmp2(p,pl,p2);
kmp1(ps,pl+sl,p3),kmp2(sp,sl+pl,p4);
kmp1(pt,pl+tl,p5),kmp1(tp,tl+pl,p6);
kmp1(t,tl,p7);
init();
solve1(),solve2(),solve3();
solve4(),solve5(),solve6();
int mx=*max_element(ans,ans+1+sl),cnt=0,fi=-1,ed=-1;
for(int i=0;i<=sl;i++)if(ans[i]==mx){
cnt++,fi=~fi?fi:i,ed=i;
}
printf("%d %d %d %d\n",mx,cnt,fi,ed);
return 0;
}//TLE
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 26436kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 1 6 6
result:
wrong answer 2nd numbers differ - expected: '2', found: '1'