結果

問題 No.515 典型LCP
ユーザー kurenai3110kurenai3110
提出日時 2017-05-09 18:56:50
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 373 ms / 1,000 ms
コード長 3,465 bytes
コンパイル時間 859 ms
コンパイル使用メモリ 82,936 KB
実行使用メモリ 89,760 KB
最終ジャッジ日時 2023-10-12 21:49:15
合計ジャッジ時間 4,399 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 359 ms
89,564 KB
testcase_01 AC 373 ms
89,760 KB
testcase_02 AC 128 ms
51,008 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 108 ms
51,208 KB
testcase_06 AC 108 ms
51,260 KB
testcase_07 AC 108 ms
51,252 KB
testcase_08 AC 117 ms
51,256 KB
testcase_09 AC 113 ms
51,800 KB
testcase_10 AC 117 ms
51,680 KB
testcase_11 AC 116 ms
51,696 KB
testcase_12 AC 117 ms
51,784 KB
testcase_13 AC 114 ms
50,892 KB
testcase_14 AC 19 ms
4,676 KB
testcase_15 AC 107 ms
51,008 KB
testcase_16 AC 107 ms
50,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define int long long

//区間内の最小値、最大値のインデックスを持つテーブル
struct sparce_table {
	vector<int> A, B, log_table;
	vector<vector<int>> tableA, tableB;
	int N;

	sparce_table(int n) {
		N = n;
		A.resize(N-1);
		B.resize(N-1);
		//for (int i = 0; i < N; i++)cin >> A[i];
		//for (int i = 0; i < N; i++)cin >> B[i];

		//対数計算は先にやっておく
		log_table.resize(N);
		for (int i = 2; i < N; i++) {
			log_table[i] = log_table[i >> 1] + 1;
		}

		tableA.resize(N-1);
		tableB.resize(N-1);
		for (int i = 0; i < N-1; i++) {
			tableA[i].resize(log_table[N-1] + 1);
			tableB[i].resize(log_table[N-1] + 1);
		}

		//区間[i,i]
		for (int i = 0; i < N-1; i++) {
			tableA[i][0] = i;
			tableB[i][0] = i;
		}
	}

	void update(){
		//区間[i,i+2^k)の計算
		for (int k = 1; (1 << k) <= N-1; k++) {
			for (int i = 0; i + (1 << k) <= N-1; i++) {
				//区間[i,i+2^(k-1))と区間[i+2^(k-1),i+2^k)の最小値、最大値のインデックス
				int firstA = tableA[i][k - 1];
				int secondA = tableA[i + (1 << (k - 1))][k - 1];
				int firstB = tableB[i][k - 1];
				int secondB = tableB[i + (1 << (k - 1))][k - 1];

				
				//最後に出てきた最大値
				if (A[firstA] > A[secondA]) {
					tableA[i][k] = firstA;
				}
				else {
					tableA[i][k] = secondA;
				}
				

				//最後に出てきた最小値
				if (B[firstB] < B[secondB]) {
					tableB[i][k] = firstB;
				}
				else {
					tableB[i][k] = secondB;
				}
			}

		}
	}

	void push(int k, int a) {
		B[k] = a;
	}

	//区間[s,t]内の最小値、最大値のインデックスを返す
	int query(int s, int t) {
		int d = t - s + 1;
		int k = log_table[d];

		pair<int, int>res = make_pair(0, 0);

		//区間[s,t]は区間[s,s+2^k)と[t-2^k+1,t)でカバーできる
		if (A[tableA[s][k]] > A[tableA[t - (1 << k) + 1][k]]) {
			res.first = tableA[s][k];
		}
		else {
			res.first = tableA[t - (1 << k) + 1][k];
		}
		
		if (B[tableB[s][k]] < B[tableB[t - (1 << k) + 1][k]]) {
			res.second = tableB[s][k];
		}
		else {
			res.second = tableB[t - (1 << k) + 1][k];
		}

		return B[res.second];
	}
};

vector<pair<int, int>> ready(int n, int M, int x, int d) {
	vector<pair<int, int>>ij(M);
	for (int k = 0; k<M; k++) {
		ij[k].first = (x / (n - 1)) + 1;
		ij[k].second = (x % (n - 1)) + 1;
		if (ij[k].first > ij[k].second) {
			swap(ij[k].first, ij[k].second);
		}
		else {
			ij[k].second = ij[k].second + 1;
		}
		x = (x + d) % (n * (n - 1));
	}
	return ij;
}

signed main() {
	int N; cin >> N;
	vector<pair<string,int>>S(N);
	for (int i = 0; i<N; i++) {
		cin >> S[i].first;
		S[i].second = i;
	}
	int M, x, d; cin >> M >> x >> d;
	long long sum = 0;

	vector<pair<int, int>>ij = ready(N, M, x, d);

	sort(S.begin(), S.end());
	vector<int>order(N);
	for (int i = 0; i < N; i++) {
		order[S[i].second] = i;
	}

	sparce_table st(N);

	for (int i = 0; i < N - 1; i++) {
		bool flag = true;
		for (int j = 0; j < min(S[i].first.size(), S[i + 1].first.size());j++) {
			if (S[i].first[j] != S[i + 1].first[j]) {
				st.push(i, j);
				flag = false;
				break;
			}
		}
		if (flag)st.push(i, min(S[i].first.size(), S[i + 1].first.size()));
	}

	st.update();

	for (int k = 0; k<M; k++) {
		int i = order[ij[k].first-1];
		int j = order[ij[k].second-1];
		if (i > j)swap(i, j);

		sum += st.query(i, j-1);
	}

	cout << sum << endl;

	return 0;
}
0