結果

問題 No.515 典型LCP
コンテスト
ユーザー creep04
提出日時 2018-03-15 13:05:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 559 ms / 1,000 ms
コード長 1,398 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,771 ms
コンパイル使用メモリ 174,952 KB
実行使用メモリ 28,876 KB
最終ジャッジ日時 2024-12-16 07:29:55
合計ジャッジ時間 5,897 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In instantiation of ‘SPA<V>::SPA(int) [with V = int]’:
main.cpp:26:20:   required from here
main.cpp:8:72: warning: integer overflow in expression of type ‘int’ results in ‘2147483647’ [-Woverflow]
    8 |         SPA(int sz) { sp = vector<vector<V> >(sz, vector<V>(30, (1<<31)-1));}
      |                                                                 ~~~~~~~^~

ソースコード

diff #
raw source code 

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

template<typename V> struct SPA {
	private:
	vector<vector<V> > sp;
	public:
	SPA(int sz) { sp = vector<vector<V> >(sz, vector<V>(30, (1<<31)-1));}
	void init(int n, V a[]) {
		for (int i = 0; i < n; ++i) sp[i][0] = a[i];
		for (int k = 1; k < 30; ++k)
			for (int i = 0; i < n-1; ++i)
				if (i+(1<<(k-1))<n) sp[i][k] = min(sp[i][k-1], sp[i+(1<<(k-1))][k-1]);
	}
	V query(int l, int r) { // min [l,r)
		int m = 0;
		while (1<<(1+m)<=r-l) m++;
		return min(sp[l][m], sp[r-(1<<m)][m]);
	}
};

int n, r[114514], a[114514];
long long m, x, d, ans;
string s[114514];
vector<pair<string,int>> p;
SPA<int> spa(114514);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
		p.push_back({s[i],i});
	}
	
	sort(p.begin(), p.end());
	for (int i = 0; i < n; ++i) r[p[i].second] = i;
	
	for (int i = 0; i < n-1; ++i) {
		int j = 0;
		for (; j < min(p[i].first.size(), p[i+1].first.size()); ++j) {
			if (p[i].first[j]!=p[i+1].first[j]) break;
		}
		a[i] = j;
	}
	spa.init(n,a);
	cin >> m >> x >> d;
	for (int i = 1; i <= m; ++i) {
		long long a = x/(n-1), b = x%(n-1);
		if (a>b) swap(a,b);
		else b++;
		x = (x+d) % ((long long)n*(n-1));
		int ra = r[a], rb = r[b];
		if (ra>rb) swap(ra,rb);
		//cout << a << ' ' << b << ' ' << lcp.q(ra,rb) << endl;
		ans += spa.query(ra,rb);
	}
	cout << ans << endl;
}
0