結果

問題 No.515 典型LCP
ユーザー creep04creep04
提出日時 2018-03-15 13:04:27
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,387 bytes
コンパイル時間 1,729 ms
コンパイル使用メモリ 177,112 KB
実行使用メモリ 31,720 KB
最終ジャッジ日時 2024-05-09 16:48:13
合計ジャッジ時間 5,798 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 168 ms
25,356 KB
testcase_03 AC 22 ms
23,812 KB
testcase_04 AC 21 ms
23,768 KB
testcase_05 AC 108 ms
25,668 KB
testcase_06 AC 114 ms
25,748 KB
testcase_07 AC 109 ms
25,616 KB
testcase_08 AC 148 ms
25,608 KB
testcase_09 AC 118 ms
25,568 KB
testcase_10 AC 117 ms
25,424 KB
testcase_11 AC 116 ms
25,496 KB
testcase_12 AC 114 ms
25,548 KB
testcase_13 AC 111 ms
25,628 KB
testcase_14 AC 27 ms
25,544 KB
testcase_15 AC 100 ms
25,624 KB
testcase_16 AC 98 ms
25,592 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

#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) % (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