結果

問題 No.515 典型LCP
コンテスト
ユーザー akun0716
提出日時 2021-01-17 20:32:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,651 bytes
コンパイル時間 1,200 ms
コンパイル使用メモリ 98,468 KB
実行使用メモリ 512,464 KB
最終ジャッジ日時 2024-11-30 01:53:48
合計ジャッジ時間 26,803 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 14 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
#define double long double
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
#define eps 1e-12 
//priority_queue<int,vector<int>, greater<int> > q2;
template<class MeetSemiLattice> struct SparseTable {
	vector<vector<MeetSemiLattice> > dat;
	vector<int> height;

	SparseTable() { }
	SparseTable(const vector<MeetSemiLattice> &vec) { init(vec); }
	void init(const vector<MeetSemiLattice> &vec) {
		int n = (int)vec.size(), h = 0;
		while ((1 << h) < n) ++h;
		dat.assign(h, vector<MeetSemiLattice>(1 << h));
		height.assign(n + 1, 0);
		for (int i = 2; i <= n; i++) height[i] = height[i >> 1] + 1;
		for (int i = 0; i < n; ++i) dat[0][i] = vec[i];
		for (int i = 1; i < h; ++i)
			for (int j = 0; j < n; ++j)
				dat[i][j] = min(dat[i - 1][j], dat[i - 1][min(j + (1 << (i - 1)), n - 1)]);
	}

	MeetSemiLattice get(int a, int b) {
		return min(dat[height[b - a]][a], dat[height[b - a]][b - (1 << height[b - a])]);
	}
};


// Suffix Array ( Manber&Myers: O(n (logn)^2) )
struct SuffixArray {
	string str;
	vector<int> sa;         // sa[i] : the starting index of the i-th smallest suffix (i = 0, 1, ..., n)
	vector<int> lcp;        // lcp[i]: the lcp of sa[i] and sa[i+1] (i = 0, 1, ..., n-1)
	inline int& operator [] (int i) { return sa[i]; }

	SuffixArray(const string& str_) : str(str_) { buildSA(); calcLCP(); }
	void init(const string& str_) { str = str_; buildSA(); calcLCP(); }

	// build SA
	vector<int> rank_sa, tmp_rank_sa;
	struct CompareSA {
		int n, k;
		const vector<int> &rank;
		CompareSA(int n, int k, const vector<int> &rank_sa) : n(n), k(k), rank(rank_sa) {}
		bool operator()(int i, int j) {
			if (rank[i] != rank[j]) return (rank[i] < rank[j]);
			else {
				int rank_ik = (i + k <= n ? rank[i + k] : -1);
				int rank_jk = (j + k <= n ? rank[j + k] : -1);
				return (rank_ik < rank_jk);
			}
		}
	};
	void buildSA() {
		int n = (int)str.size();
		sa.resize(n + 1), lcp.resize(n + 1), rank_sa.resize(n + 1), tmp_rank_sa.resize(n + 1);
		for (int i = 0; i < n; ++i) sa[i] = i, rank_sa[i] = (int)str[i];
		sa[n] = n, rank_sa[n] = -1;
		for (int k = 1; k <= n; k *= 2) {
			CompareSA csa(n, k, rank_sa);
			sort(sa.begin(), sa.end(), csa);
			tmp_rank_sa[sa[0]] = 0;
			for (int i = 1; i <= n; ++i) {
				tmp_rank_sa[sa[i]] = tmp_rank_sa[sa[i - 1]];
				if (csa(sa[i - 1], sa[i])) ++tmp_rank_sa[sa[i]];
			}
			for (int i = 0; i <= n; ++i) rank_sa[i] = tmp_rank_sa[i];
		}
	}
	vector<int> rsa;
	SparseTable<int> st;
	void calcLCP() {
		int n = (int)str.size();
		rsa.resize(n + 1);
		for (int i = 0; i <= n; ++i) rsa[sa[i]] = i;
		lcp.resize(n + 1);
		lcp[0] = 0;
		int cur = 0;
		for (int i = 0; i < n; ++i) {
			int pi = sa[rsa[i] - 1];
			if (cur > 0) --cur;
			for (; pi + cur < n && i + cur < n; ++cur) {
				if (str[pi + cur] != str[i + cur]) break;
			}
			lcp[rsa[i] - 1] = cur;
		}
		st.init(lcp);
	}

	// calc lcp
	int getLCP(int a, int b) {          // lcp of str.sutstr(a) and str.substr(b)
		return st.get(min(rsa[a], rsa[b]), max(rsa[a], rsa[b]));
	}
};


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N; cin >> N;
	string S = "";
	VI A;
	int k = 0;
	A.push_back(0);
	REP(i, N) {
		string s; cin >> s;
		REP(j, s.size()) S.push_back(s[j]);
		k += s.size();
		A.push_back(k);
	}
	SuffixArray T(S);
	int M, x, d;
	int ans = 0;
	cin >> M >> x >> d;


	VI I(M + 1), J(M + 1);
	eFOR(k, 1, M) {
		I[k] = (x / (N - 1)) + 1;
		J[k] = (x % (N - 1)) + 1;
		if (I[k] > J[k])swap(I[k], J[k]);
		else J[k] = J[k] + 1;
		x = (x + d) % (N * (N - 1));
	}
	eFOR(k, 1, M) {
		int i = I[k], j = J[k];
		//cout << i << " " << j << endl;
		i--, j--;
		//cout << i << " " << j << endl;
		ans += T.getLCP(A[i], A[j]);
	}
	cout << ans << endl;
	return 0;
}
0