QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89554#5256. InsertionsdaydreamWA 25ms61160kbC++146.4kb2023-03-20 16:01:412023-03-20 16:01:43

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-20 16:01:43]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:61160kb
  • [2023-03-20 16:01:41]
  • 提交

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=1;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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 25ms
memory: 60040kb

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: 14ms
memory: 61160kb

input:

z
zzkkzzkk
z

output:

5 1 1 1

result:

wrong answer 2nd numbers differ - expected: '2', found: '1'