結果

問題 No.515 典型LCP
ユーザー kotatsugamekotatsugame
提出日時 2019-09-26 08:47:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,054 bytes
コンパイル時間 1,334 ms
コンパイル使用メモリ 92,884 KB
実行使用メモリ 30,744 KB
最終ジャッジ日時 2024-09-23 07:42:00
合計ジャッジ時間 5,757 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  133 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
using namespace std;
//construct SA by doubling O(N(log N)^2)
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
struct SA{
	string s;
	vector<int>sa,rank;
	SA(const string&s_):s(s_)
	{
		int n=s.size();
		sa.resize(n+1);
		rank.resize(n+1);
		for(int i=0;i<=n;i++)
		{
			sa[i]=i;
			rank[i]=i<n?s[i]:-1;
		}
		for(int k=1;k<=n;k<<=1)
		{
			vector<int>tmp(rank);
			function<bool(int,int)>f=[&tmp,&k,&n](int i,int j){
				return tmp[i]!=tmp[j]?tmp[i]<tmp[j]:
					(i+k<=n?tmp[i+k]:-1)<(j+k<=n?tmp[j+k]:-1);
			};
			sort(sa.begin(),sa.end(),f);
			rank[sa[0]]=0;
			for(int i=1;i<=n;i++)
			{
				rank[sa[i]]=rank[sa[i-1]]+f(sa[i-1],sa[i]);
			}
		}
	}
	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