QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188885#5256. InsertionsqzezWA 0ms26436kbC++144.0kb2023-09-26 16:07:562023-09-26 16:07:57

Judging History

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

  • [2023-09-26 16:07:57]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:26436kb
  • [2023-09-26 16:07:56]
  • 提交

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'