QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89555 | #5256. Insertions | daydream | WA | 15ms | 61156kb | C++14 | 6.4kb | 2023-03-20 16:03:00 | 2023-03-20 16:03:02 |
Judging History
answer
#include<bits/stdc++.h>
#define db double
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define LL long long
#define ldb long double
#define pdd pair<db,db>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pii pair<int,int>
#define pip pair<int,pii>
#define ppi pair<pii,int>
#define ppp pair<pii,pii>
#define pss pair<pair<char,char>,pair<char,char>>
#define fr first
#define sc second
#define mp make_pair
#define id(x,y) ((x-1)*m+y)
using namespace std;
const int mxn=2e5+10,mxm=5010,N=1e6,infi=1e9,mod=998244353,inv2=(mod+1)/2,inv3=(mod+1)/3;
const int v1=37,v2=53,M1=323323323,M2=998244353;
const int dx[]={0,1,0,-1},
dy[]={1,0,-1,0};
const db PI=acos(-1),eps=1e-10;
const LL infl=1e18;
int DB_cmp(db x,db y) {if(fabs(x-y)<eps) return 0; if(x<y) return -1; return 1;}
inline void chkmax(LL &x,const LL y) {if(y>x) x=y;}
inline void chkmax(int &x,const int y) {if(y>x) x=y;}
inline void chkmin(LL &x,const LL y) {if(y<x) x=y;}
inline void chkmin(int &x,const int y) {if(y<x) x=y;}
inline void upd(int &x,const int y) {if((x+=y)>=mod) x-=mod;}
inline int Add(const int x,const int y) {if(x+y>=mod) return x+y-mod; return x+y;}
inline LL my_gcd(LL a,LL b) {if(!a||!b) return a|b; for(LL c=a%b;c;a=b,b=c,c=a%b); return b;}
inline int _pow(int k,int i)
{
int t=1;
for(;i;i>>=1,k=1ll*k*k%mod)
if(i&1)
t=1ll*t*k%mod;
return t;
}
inline int _pow(int k,int i,int M)
{
int t=1;
for(;i;i>>=1,k=1ll*k*k%M)
if(i&1)
t=1ll*t*k%M;
return t;
}
struct SAM
{
int tim,siz[mxn],son[mxn],dep[mxn],top[mxn],dfn[mxn];
int tp,nw,ps[mxn],ln[mxn],fa[mxn],trs[mxn][27];
int f[mxn];
int t,h[mxn];
struct Tre
{
int to,nxt;
}e[mxn];
void add(int u,int v) {e[++t]=(Tre){v,h[u]};h[u]=t;}
int build(int u,int c,int i)
{
int v,x=++tp;ps[i]=x;ln[x]=ln[u]+1;
for(;u&&!trs[u][c];trs[u][c]=x,u=fa[u]);
if(!u) fa[x]=1;
else if(ln[v=trs[u][c]]==ln[u]+1) fa[x]=v;
else
{
fa[++tp]=fa[v];ln[tp]=ln[u]+1;fa[x]=fa[v]=tp;
for(int i=0;i<26;++i) trs[tp][i]=trs[v][i];
for(;u&&trs[u][c]==v;trs[u][c]=tp,u=fa[u]);
}
return x;
}
void dfs1(int u)
{
int v;siz[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
dep[v=e[i].to]=dep[u]+1;
dfs1(v);siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int Top)
{
top[u]=Top;dfn[u]=++tim;
if(son[u]) dfs2(son[u],Top);
int v;
for(int i=h[u];i;i=e[i].nxt)
if((v=e[i].to)!=son[u])
dfs2(v,v);
}
void build(char *s,int L)
{
tp=nw=1;
for(int i=L;i;--i) nw=build(nw,s[i]-'a',i);
for(int i=2;i<=tp;++i) add(fa[i],i);
dfs1(1);dfs2(1,1);
}
int lcm(int x,int y)
{
int u=ps[x],v=ps[y];
for(;top[u]!=top[v];u=fa[u])
if(dep[top[u]]<=dep[top[v]])
swap(u,v);
if(dep[u]<dep[v]) return ln[u];
return ln[v];
}
void upd(int x) {f[ps[x]]++;}
void work(int u=1)
{
int v;
for(int i=h[u];i;i=e[i].nxt)
f[v=e[i].to]+=f[u],
work(v);
}
int qry(int x) {return f[ps[x]];}
}S1,S2,S3,S4;
int n,L1,L2,L3,ans1,ans2,ans3,ans4,cnt[mxn],res[mxn];
char s[mxn],t[mxn],p[mxn],S[mxn];
map<pii,int> ex;
vector<pii> Q[mxn<<2];
vector<int> ins[mxn<<2],del[mxn<<2];
struct BIT
{
int n,tr[mxn<<2];
void upd(int i,int v) {for(;i<=n;i+=(i&-i)) tr[i]+=v;}
void upd(int l,int r,int v) {upd(l,v); upd(r+1,-v);}
int qry(int i) {int res=0; for(;i;i-=(i&-i)) res+=tr[i]; return res;}
}T;
LL rd()
{
static LL sl,fh,ch;
sl=0;fh=1;ch=getchar();
while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=getchar();}
while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
return sl*fh;
}
int main()
{
// freopen("data.in","r",stdin);
// for(int TT=rd();TT;--TT)
{
scanf("%s%s%s",s+1,t+1,p+1);
L1=strlen(s+1);L2=strlen(t+1);L3=strlen(p+1);
n=0;
for(int i=1;i<=L1;++i) S[++n]=s[i];
S[++n]='z'+1;
for(int i=1;i<=L3;++i) S[++n]=p[i];
S1.build(S,n);
n=0;
for(int i=1;i<=L3;++i) S[++n]=p[i];
S[++n]='z'+1;
for(int i=1;i<=L1;++i) S[++n]=s[i];
reverse(S+1,S+n+1);
S2.build(S,n);
int x,y;
ex.clear();
x=y=0;
for(int c,i=1;i<L3;++i)
{
c=p[i]-'a'+1;
x=(1ll*x*v1+c)%M1;
y=(1ll*y*v2+c)%M2;
ex[mp(x,y)]=i+1;
}
x=y=0;
for(int c,i=L2,vx=1,vy=1;i;--i,vx=1ll*v1*vx%M1,vy=1ll*v2*vy%M2)
{
c=t[i]-'a'+1;
x=(1ll*vx*c+x)%M1;
y=(1ll*vy*c+y)%M2;
if(ex.count(mp(x,y))) S1.upd(ex[mp(x,y)]+L1+1);
}
ex.clear();
x=y=0;
for(int c,i=L3,vx=1,vy=1;i>1;--i,vx=1ll*v1*vx%M1,vy=1ll*v2*vy%M2)
{
c=p[i]-'a'+1;
x=(1ll*vx*c+x)%M1;
y=(1ll*vy*c+y)%M2;
ex[mp(x,y)]=i-1;
}
x=y=0;
for(int c,i=1;i<=L2;++i)
{
c=t[i]-'a'+1;
x=(1ll*x*v1+c)%M1;
y=(1ll*y*v2+c)%M2;
if(ex.count(mp(x,y))) S2.upd(n-ex[mp(x,y)]+1);
}
S1.work();S2.work();
for(int i=1;i<=L1;++i) cnt[i]=cnt[i-1]+(S1.lcm(i,L1+2)==L3);
// for(int i=1;i<=L1;++i) printf("%d ",S1.lcm(i,L1+2)==L3);puts("");
for(int i=0;i<=L1;++i)
{
res[i]+=cnt[L1]-cnt[i];
if(i-L3+1>=0) res[i]+=cnt[i-L3+1];
res[i]+=S1.qry(i+1)+S2.qry(n-i-L3);
}
if(L3<=L2)
{
n=0;
for(int i=1;i<=L2;++i) S[++n]=t[i];
S[++n]='z'+1;
for(int i=1;i<=L3;++i) S[++n]=p[i];
S3.build(S,n);
int num=0;
for(int i=1;i<=L2;++i) num+=(S3.lcm(i,L2+2)==L3);
for(int i=0;i<=L1;++i) res[i]+=num;
}
else if(L3>=L2+2)
{
T.n=S2.tp;
x=y=0;int vx=1,vy=1;
for(int c,i=1;i<=L2;++i)
{
c=t[i]-'a'+1;
x=(1ll*x*v1+c)%M1;
y=(1ll*y*v2+c)%M2;
vx=1ll*vx*v1%M1;vy=1ll*vy*v2%M2;
}
pii ht=mp(x,y);vx=M1-vx;vy=M2-vy;
for(int c,i=1;i<=L2;++i)
{
c=p[i]-'a'+1;
x=(1ll*x*v1+c)%M1;
y=(1ll*y*v2+c)%M2;
}
int u,v;
for(int c,i=L2+1;i<L3;++i)
{
c=p[i]-'a'+1;
x=(1ll*x*v1+c)%M1;
y=(1ll*y*v2+c)%M2;
c=p[i-L2]-'a'+1;
x=(1ll*vx*c+x)%M1;
y=(1ll*vy*c+y)%M2;
if(mp(x,y)==ht)
{
u=S1.ps[i+1+L1+1];
v=S2.ps[n-(i-L2)+1];
ins[S1.dfn[u]].pb(v);
del[S1.dfn[u]+S1.siz[u]].pb(v);
}
}
for(int i=1;i<L1;++i) Q[S1.ps[i+1]].pb({i,S2.ps[n-i-L3]});
for(int i=1;i<=S1.tp;++i)
{
for(auto u:ins[i]) T.upd(S2.dfn[u],S2.dfn[u]+S2.siz[u]-1,1);
for(auto u:del[i]) T.upd(S2.dfn[u],S2.dfn[u]+S2.siz[u]-1,-1);
for(auto x:Q[i]) res[x.fr]+=T.qry(S2.dfn[x.sc]);
}
}
ans1=-1;
for(int i=0;i<=L1;++i)
{
if(res[i]>ans1) ans1=res[i],ans2=1,ans3=ans4=i;
else if(res[i]==ans1) ans2++,ans4=i;
}
printf("%d %d %d %d\n",ans1,ans2,ans3,ans4);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 12ms
memory: 60992kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 2 6 7
result:
ok 4 number(s): "2 2 6 7"
Test #2:
score: 0
Accepted
time: 4ms
memory: 61156kb
input:
z zzkkzzkk z
output:
5 2 0 1
result:
ok 4 number(s): "5 2 0 1"
Test #3:
score: -100
Wrong Answer
time: 15ms
memory: 61148kb
input:
wgwwggggw g gggg
output:
2 2 4 8
result:
wrong answer 2nd numbers differ - expected: '5', found: '2'