結果

問題 No.515 典型LCP
ユーザー claw88
提出日時 2017-07-13 12:35:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 266 ms / 1,000 ms
コード長 1,925 bytes
コンパイル時間 1,792 ms
コンパイル使用メモリ 106,808 KB
実行使用メモリ 26,096 KB
最終ジャッジ日時 2024-10-07 18:08:19
合計ジャッジ時間 5,139 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec; typedef pair<string, int> pi;
int dd[] = { 0, 1, 0, -1, 0 };

int N;
pi P[114514];
string S[114514];
int ID[114514];
#define M 200010
#define K 18
int st[K][M];
int lcp[114514];

void construct(int *a, int n)
{
	copy_n(a, n, st[0]);
	for (int k = 1; k < K; k++)
	{
		for (int i = 0; i + (1 << k) <= n; i++)
		{
			st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
		}
	}
}
int query(int a, int b)
{
	int k = 31 - __builtin_clz(b - a);
	return min(st[k][a], st[k][b - (1 << k)]);
}
int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> S[i];
		P[i] = { S[i] , i };
	}
	sort(P, P + N);
	sort(S, S + N);
	for (int i = 0; i < N; i++)
	{
		ID[P[i].second] = i;
	}
	for(int i=1;i<N;i++)
	{
		int cnt = 0;
		for(int j=0;j<S[i-1].size()&&j<S[i].size();j++)
		{
			if(S[i-1][j]==S[i][j])cnt++;
			else break;
		}
		lcp[i-1]=cnt;
	}
	construct(lcp, N-1);
	
	/*for(int i = 0; i < N; i++)
	{
		cout << ID[i] << " " << P[i].second << endl;;
	}
	cout << endl;
	/*
	for(int j = 0; j < 4; j++)
	{
		for(int i = 0; i < N - 1; i++)
		{
			cout << st[j][i] << " ";
		}
		cout << endl;
	}*/
	
	int W; i64 x, d;
	cin >> W >> x >> d;
	i64 ans = 0;
	for(int i =0; i<W;i++)
	{
		int P = x / (N-1);
		int Q = x % (N-1);
		if(P>Q) swap(P,Q);
		else Q++;
		
		int  a = ID[P];
		int  b = ID[Q];
		if(a> b)swap(a, b);
		
		//cout << P << " " << Q << endl;
		//cout << a << " " << b << endl;
		ans += query(a,b);
		//cout << ans << endl;
		x = (x +d)% ((i64)N * (N-1));
	}
	cout << ans << endl;

	return 0;
}
0