QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#357839#5256. InsertionszaaCompile Error//C++144.8kb2024-03-19 13:48:032024-03-19 13:48:03

Judging History

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

  • [2024-03-19 13:48:03]
  • 评测
查看
  • [2024-03-19 13:48:03]
  • 提交

answer

#include <cstdio>

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#include <emmintrin.h>
#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;
}
Source code, Language: C++14

Details 

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
                 from /usr/include/c++/13/ext/atomicity.h:35,
                 from /usr/include/c++/13/bits/ios_base.h:39,
                 from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
                 from answer.code:7:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1: error: attribute value ‘t...
English 繁體中文 简体中文

Server Time: 2024-12-04 11:03:03 | OpenSource Project