結果

問題 No.515 典型LCP
コンテスト
ユーザー kurenai3110
提出日時 2017-05-09 18:44:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,332 bytes
コンパイル時間 962 ms
コンパイル使用メモリ 80,876 KB
実行使用メモリ 52,560 KB
最終ジャッジ日時 2024-09-14 20:03:55
合計ジャッジ時間 3,386 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

//区間内の最小値、最大値のインデックスを持つテーブル
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;
}

int 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++) {
		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);
				break;
			}
		}
	}

	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