結果

問題 No.515 典型LCP
ユーザー kotatsugamekotatsugame
提出日時 2019-09-26 08:46:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 650 ms / 1,000 ms
コード長 4,509 bytes
コンパイル時間 1,240 ms
コンパイル使用メモリ 90,868 KB
実行使用メモリ 85,460 KB
最終ジャッジ日時 2024-09-23 07:41:54
合計ジャッジ時間 7,572 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 650 ms
85,332 KB
testcase_01 AC 493 ms
81,788 KB
testcase_02 AC 315 ms
79,872 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 331 ms
84,416 KB
testcase_06 AC 326 ms
85,460 KB
testcase_07 AC 329 ms
79,196 KB
testcase_08 AC 361 ms
84,600 KB
testcase_09 AC 253 ms
77,672 KB
testcase_10 AC 254 ms
79,968 KB
testcase_11 AC 254 ms
80,164 KB
testcase_12 AC 257 ms
80,036 KB
testcase_13 AC 254 ms
79,864 KB
testcase_14 AC 150 ms
80,948 KB
testcase_15 AC 319 ms
84,468 KB
testcase_16 AC 316 ms
81,316 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:202:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  202 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
using namespace std;
//construct SA by SA-IS O(N)
#include<string>
#include<vector>
struct SA{
	string s;
	vector<int>sa;
	SA(const string&s_):s(s_)
	{
		sa=build(vector<int>(s.begin(),s.end()),256);
	}
	vector<int>induced_sort(const vector<int>&S,const vector<int>&id,const vector<bool>&SL,vector<int>last)
	{
		vector<int>first(last);
		vector<int>ret(id.size());
		ret[0]=id[0];
		for(int i=0;i<id.size();i++)
		{
			if(id[i]>=1&&!SL[id[i]-1])
			{
				ret[first[S[id[i]-1]-1]++]=id[i]-1;
			}
			else if(ret[i]>=1&&!SL[ret[i]-1])
			{
				ret[first[S[ret[i]-1]-1]++]=ret[i]-1;
			}
		}
		for(int i=id.size();i--;)
		{
			if(ret[i]>=1&&SL[ret[i]-1])
			{
				ret[--last[S[ret[i]-1]]]=ret[i]-1;
			}
		}
		return ret;
	}
	vector<int>build(vector<int>S,int maxval)
	{
		if(S.size()<=1)
		{
			return S.empty()?(vector<int>){0}:(vector<int>){1,0};
		}
		S.push_back(0);
		vector<int>cnt(maxval,0);
		vector<bool>SL(S.size());//S=>true,L=>false
		for(int i=S.size();i--;)
		{
			cnt[S[i]]+=1;
			SL[i]=i+1==S.size()||S[i]<S[i+1]||S[i]==S[i+1]&&SL[i+1];
		}
		for(int i=1;i<maxval;i++)cnt[i]+=cnt[i-1];
		vector<int>last(cnt);
		vector<int>id(S.size());
		vector<int>is_LMS(S.size());
		int LMScnt=0;
		for(int i=1;i<S.size();i++)
		{
			if(!SL[i-1]&&SL[i])
			{
				is_LMS[i]=1;
				id[--cnt[S[i]]]=i;
				LMScnt+=1;
			}
		}
		id=induced_sort(S,id,SL,last);
		int LMSsub=1;
		int pre=-1;
		is_LMS[id[0]]=LMSsub++;
		for(int i=1;i<id.size();i++)
		{
			if(is_LMS[id[i]])
			{
				if(pre>=0&&S[pre]==S[id[i]])
				{
					int k;
					for(k=1;S[pre+k]==S[id[i]+k]&&!is_LMS[pre+k]&&!is_LMS[id[i]+k];k++);
					LMSsub-=S[pre+k]==S[id[i]+k]&&is_LMS[pre+k]&&is_LMS[id[i]+k];
				}
				pre=id[i];
				is_LMS[id[i]]=LMSsub++;
			}
		}
		vector<int>newstr(LMScnt);
		vector<int>rev(LMScnt);
		int counter=0;
		for(int i=0;i<S.size();i++)
		{
			if(is_LMS[i])
			{
				newstr[counter]=is_LMS[i];
				rev[counter]=i;
				counter+=1;
			}
		}
		vector<int>sortedLMS=build(newstr,LMSsub);
		id.assign(S.size(),0);
		for(int i=1;i<sortedLMS.size();i++)
		{
			int I=rev[sortedLMS[i]];
			id[cnt[S[I]]++]=I;
		}
		return induced_sort(S,id,SL,last);
	}
	int operator[](int i)const{return sa[i];}
	int lower_bound(const string&t)const
	{
		int L=-1,R=sa.size();
		while(R-L>1)
		{
			int M=L+R>>1;
			if(s.compare(sa[M],t.size(),t)>=0)R=M;
			else L=M;
		}
		return R;
	}
	int upper_bound(const string&t)const
	{
		int L=-1,R=sa.size();
		while(R-L>1)
		{
			int M=L+R>>1;
			if(s.compare(sa[M],t.size(),t)<=0)L=M;
			else R=M;
		}
		return R;
	}
	bool contain(const string&t)const
	{
		int id=lower_bound(t);
		return id<sa.size()&&s.compare(sa[id],t.size(),t)==0;
	}
	int size()const{return sa.size();}
};
//construct LCP O(N) require SA
struct LCP{
	vector<int>lcp;
	LCP(const SA&sa)
	{
		int n=sa.size()-1;
		lcp.assign(n,0);
		vector<int>rank(n+1);
		for(int i=0;i<=n;i++)rank[sa[i]]=i;
		int h=0;
		lcp[0]=0;
		for(int i=0;i<n;i++)
		{
			int j=sa[rank[i]-1];
			h-=h>0;
			for(;i+h<n&&j+h<n&&sa.s[i+h]==sa.s[j+h];h++);
			lcp[rank[i]-1]=h;
		}
	}
	int operator[](int i)const{return lcp[i];}
	int size()const{return lcp.size();}
};
//Disjoint Sparse Table
#include<vector>
#include<functional>
template<typename T>
struct DST{
	function<T(T,T)>calcfn;
	int n;
	vector<vector<T> >dat;
	DST(const vector<T>&v={},
		function<T(T,T)>calcfn_=[](T a,T b){return a<b?a:b;}
	):calcfn(calcfn_)
	{
		n=v.size();
		dat.push_back(v);
		for(int i=2;i<n;i<<=1)
		{
			dat.push_back(vector<T>(n));
			for(int j=i;j<n;j+=i<<1)
			{
				dat.back()[j-1]=dat[0][j-1];
				for(int k=2;k<=i;k++)
				{
					dat.back()[j-k]=calcfn(dat[0][j-k],dat.back()[j-k+1]);
				}
				dat.back()[j]=dat[0][j];
				for(int k=2;k<=i&&j+k<=n;k++)
				{
					dat.back()[j+k-1]=calcfn(dat[0][j+k-1],dat.back()[j+k-2]);
				}
			}
		}
	}
	T query(int l,int r)const//[l,r)
	{
		if(l<0)l=0;
		if(r>n)r=n;
		r--;
		if(l==r)return dat[0][l];
		int k=31-__builtin_clz(l^r);
		return calcfn(dat[k][l],dat[k][r]);
	}
};
int id[1<<17];
int rev[1<<20];
int len[1<<17];
main()
{
	int N;
	cin>>N;
	string s="";
	for(int i=0;i<N;i++)
	{
		string t;cin>>t;
		id[i]=s.size();
		len[i]=t.size();
		s+=t;
	}
	SA P(s);
	for(int i=0;i<P.size();i++)rev[P[i]]=i;
	LCP Q(P);
	DST<int>X(Q.lcp);
	int M;
	long x,d;
	cin>>M>>x>>d;
	long ans=0;
	for(;M--;)
	{
		int i=x/(N-1),j=x%(N-1);
		if(i>j)i^=j^=i^=j;
		else j++;
		int I=rev[id[i]],J=rev[id[j]];
		if(I>J)I^=J^=I^=J;
		ans+=min(X.query(I,J),min(len[i],len[j]));
		x=(x+d)%((long)N*(N-1));
	}
	cout<<ans<<endl;
}
0