QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#357840 | #5256. Insertions | zaa | WA | 8ms | 50972kb | C++20 | 4.6kb | 2024-03-19 13:49:01 | 2024-03-19 13:49:03 |
Judging History
answer
#include<bits/stdc++.h>
//~ #define int long long
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i, b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=3e5+5,Mod=998244353;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
//inline void Add(int &x,int y){(x=x+y+Mod)%Mod;}
//~ typedef __int128_t i128;
//~ i128 _base=1;
//~ inline int mol(int x){return x-Mod*(_base*x>>64);}
inline int read(){
int f=0,x=0;
char ch=getchar();
while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f?-x:x;
}
string s,t,p;
int n1,n2,n3;
struct SuffixArray {
char s[N];
int n,m;
int rak[N],tp[N],tag[N],sa[N];
int height[N];
int st[N][21];
inline int log(int pp){
int xx=0;
while(pp!=0){
pp>>=1;
xx++;
}
return xx;
}
inline void SA(){
m=500;
For(i,0,m) tag[i]=0;
For(i,1,n) rak[i]=(int)s[i];
int p=0;
For(i,1,n)++tag[rak[i]];
For(i,1,m) tag[i]+=tag[i-1];
for(int i=n;i>=1;--i) sa[tag[rak[i]]--]=i;
for(int k=1;k<=n;k<<=1){
p=0;
For(i,0,m) tag[i]=tp[i]=0;
For(i,n-k+1,n) tp[++p]=i;
For(i,1,n)
if(sa[i]>k)
tp[++p]=sa[i]-k;
For(i,1,m) tag[i]=0;
For(i,1,n)tag[rak[i]]++;
For(i,1,m) tag[i]+=tag[i-1];
Rof(i,n,1) sa[tag[rak[tp[i]]]--]=tp[i],tp[i]=0;
swap(rak,tp);
rak[sa[1]]=1;
p=1;
For(i,2,n)
rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+k]==tp[sa[i]+k])?p:++p;
m=p;
}
int k=0;
For(i,1,n){
if(k) k--;
while(s[i+k]==s[sa[rak[i]-1]+k]) ++k;
height[rak[i]]=k;
}
For(i,1,n) st[i][0]=height[i];
For(j,1,20)
for(int i=1;i<=n&&i+(1<<j)-1<=n;++i)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
inline int gets(int l,int r){
int x=rak[l],y=rak[r];
if(x>y) swap(x,y);
x++;
int k=log2(y-x+1);
return min(st[x][k],st[y-(1<<k)+1][k]);
}
}A,B;
set<int>l[N],r[N];
bitset<100005>ggl,ggr,s1;
int vis[N],bk[N];
int tp1,tp2;
int ans[N];
signed main(){
//~ _base=(_base<<64)/Mod;
//~ freopen("lgs5.in","r",stdin);
//~ freopen("lgs.out","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
cin>>s>>t>>p;
n1=s.size(),n2=t.size(),n3=p.size();
//~ cout<<1;
//~ cout<<n1<<" "<<n2<<" "<<n3<<endl;
B.n=A.n=n1+1+n2+1+n3;
int tot=0;
For(i,1,n1) A.s[++tot]=s[i-1];
A.s[++tot]='z'+1;
int gg1=tot;
For(i,1,n2) A.s[++tot]=t[i-1];
A.s[++tot]='z'+1;
int wz=tot+1;
For(i,1,n3) A.s[++tot]=p[i-1];
tot=0;
Rof(i,n1,1) B.s[++tot]=s[i-1];
B.s[++tot]='z'+1;
Rof(i,n2,1) B.s[++tot]=t[i-1];
B.s[++tot]='z'+1;
Rof(i,n3,1) B.s[++tot]=p[i-1];
A.SA();B.SA();
int gg=0;
For(i,1,n1){
l[i+A.gets(i,wz)-1].insert(A.gets(i,wz));
r[n1-i+1-B.gets(i,wz)+1].insert(B.gets(i,wz));
if(A.gets(i,wz)==n3) vis[i+n3-1]=1,bk[i]=1,gg++;
//~ cout<<A.gets(i,wz)<<" "<<B.gets(i,wz)<<endl;
}
For(i,1,n2){
int p=gg1+i;
int ll=A.gets(p,wz);
int rr=B.gets(p,wz);
if(ll==n3){
gg++;
}
if(i+ll-1>=n2&&ll) ggl[n3-(ll-((i+ll-1)-n2))]=1;
if(n2-i+1-rr<=0&&rr) ggr[n3-(rr-(n2-i+1-rr))]=1;
//~ cout<<ll<<" "<<rr<<endl;
}
//~ cout<<gg<<endl;
ggr[0]=0;
ggl[0]=0;
ggr[n3]=0;
ggl[n3]=0;
//~ cout<<endl;
//~ For(i,1,n3) cout<<ggl[i]<<" "<<ggr[i]<<endl;
int res=gg;
ans[0]=res;
For(i,1,n1+1){
if(bk[i]==1) res--;
if(vis[i]==1) res++;
for(auto j:r[i])s1.set(j);
//~ cout<<r[i]<<s1[r[i]]<<endl;
ans[i]=res;
int x=(s1&ggl).count();
if(x){
ans[i-1]+=x;
//~ cout<<"Yes";
}
//~ For(j,0,n1) cout<<s1[j]<<" ";
//~ cout<<endl;
s1>>=1;
}
//~ cout<<endl;
//~ For(i,1,n3) cout<<ggl[i]<<" ";
//~ For(i,1,n3) cout<<ggr[i]<<" ";
//~ cout<<(ss.count())<<endl;
s1.reset();
Rof(i,n1+1,0){
for(auto j:l[i])s1.set(j);
int x=((s1&ggr).count());
if(x){
ans[i]+=x;
//~ cout<<((s2&ggr).count())<<" ";
//~ cout<<"Yes";
}
s1>>=1;
}
//~ For(i,0,n1+1){
//~ printf("%lld ",ans[i]);
//~ }
int l=0,r=0,maxx=0,num=0;
For(i,0,n1+1){
if(ans[i]>maxx){
l=i,r=i;
maxx=ans[i];
num=0;
}
if(ans[i]==maxx){
num++;
r=max(r,i);
}
}
if(maxx==0) l=r=num=0;
printf("%d %d %d %d\n",maxx,num,l,r);
#ifdef LOCAL
Debug("\nMy Time: %.3lfs\n", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 48864kb
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: 8ms
memory: 50972kb
input:
z zzkkzzkk z
output:
5 3 0 2
result:
wrong answer 2nd numbers differ - expected: '2', found: '3'