結果

問題 No.515 典型LCP
コンテスト
ユーザー gigime
提出日時 2017-05-06 00:12:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,529 bytes
コンパイル時間 2,733 ms
コンパイル使用メモリ 197,052 KB
実行使用メモリ 56,348 KB
最終ジャッジ日時 2024-09-14 10:06:14
合計ジャッジ時間 7,065 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

const ll pow1 = 1003,pow2 = 1007,mod1 = 1e9 + 7,mod2 = 1e9 + 9;

struct RollingHash{
	int n;
	vector<ll> dat,powTable;
	ll pow,mod;
	void init(string& str,ll pow,ll mod){
		n = str.size();
		this->pow = pow;
		this->mod = mod;
		dat.assign(n + 1,0);
		powTable.assign(n + 1,1);
		for(int i = 1;i <= n;i++){
			dat [i] = (dat [i - 1] * pow + str [i - 1]) % mod;
			powTable [i] = powTable [i - 1] * pow % mod;
		}
	}
	ll get(int l,int r){
		ll res = dat [r] - dat [l] * powTable [r - l];
		res = (res % mod + mod) % mod;
		return res;
	}
};

struct SparseTable{
	int n;
	vector< vector<int> > dat;
	vector<int> logTable;
	void init(vector<int>& v){
		n = v.size();
		logTable.assign(n + 1,0);
		logTable [1] = 0;
		for(int i = 2;i <= n;i++){
			logTable [i] = logTable [i / 2] + 1;
		}
		dat.assign(logTable [n] + 1,vector<int>(n));
		for(int i = 0;i < n;i++) dat [0] [i] = v [i];
		for(int i = 1;i <= logTable [n];i++){
			for(int j = 0;j < n;j++){
				dat [i] [j] = min(dat [i - 1] [j],dat [i - 1] [j + (1 << (i - 1))]);
			}
		}
	}
	int getMin(int l,int r){
		int x = logTable [r - l];
		return min(dat [x] [l],dat [x] [r - (1 << x)]);
	}
};

int N;
vector< pair<string,int> > S;
RollingHash rh [100000];
char buffer [1000000];
ll M,X,D;
const int INF = 1e9;

void get_query(int& a,int& b)
{
	a = (X / (N - 1)) + 1;
	b = (X % (N - 1)) + 1;
	if(a > b){
		swap(a,b);
	}
	else{
		b++;
	}
	X = (X + D) % (N * (N - 1));
}

int main()
{
	scanf("%d",&N);
	S.assign(N,make_pair("",0));
	FOR(i,0,N){
		scanf("%s",buffer);
		S [i] = {buffer,i};
	}
	scanf("%lld%lld%lld",&M,&X,&D);
	sort(S.begin(),S.end());
	map<int,int> mp;
	FOR(i,0,N){
		rh [i].init(S [i].first,pow1,mod1);
		mp [S [i].second] = i;
	}
	vector<int> v;
	FOR(i,0,N - 1){
		int ok = 0,ng = min(S [i].first.size(),S [i + 1].first.size()) + 1,mid;
		while(ng - ok > 1){
			mid = (ok + ng) / 2;
			if(rh [i].get(0,mid) == rh [i + 1].get(0,mid)){
				ok = mid;
			}
			else{
				ng = mid;
			}
		}
		v.push_back(ok);
	}
	
	SparseTable st;
	st.init(v);
	
	ll ans = 0;
	FOR(i,0,M){
		int a,b;
		get_query(a,b);
		a--; b--;
		a = mp [a]; b = mp [b];
		if(a > b) swap(a,b);
		ans += st.getMin(a,b);
	}
	printf("%lld\n",ans);

	return 0;
}
0