結果

問題 No.515 典型LCP
コンテスト
ユーザー vjudge1
提出日時 2025-03-16 23:26:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 516 ms / 1,000 ms
コード長 1,088 bytes
コンパイル時間 1,510 ms
コンパイル使用メモリ 162,284 KB
実行使用メモリ 311,736 KB
最終ジャッジ日時 2025-03-16 23:26:25
合計ジャッジ時間 7,916 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3000010;
int n, i[N], j[N],m,x,d;
unsigned int p[N],p2[N];
string s[N];
vector<unsigned int> v[N];
vector<unsigned int> v2[N];
signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++ ) cin >> s[i],s[i]=' '+s[i];
	cin>>m>>x>>d;
	for(int k=1;k<=m;k++) {
		i[k] = (x / (n - 1)) + 1;
	  j[k] = (x % (n - 1)) + 1;
	  if (i[k] > j[k])
	    swap(i[k], j[k]);
	  else
	    j[k] = j[k] + 1;
		
		x = (x + d) % (n * (n - 1));
	}
	for(int i=1;i<=n;i++) {
		v[i].resize(s[i].size()+5);
		v2[i].resize(s[i].size()+5);
		p[0]=1;p2[0]=1;
		for(int j=1;j<s[i].size();j++) {
			v[i][j]=v[i][j-1]*31+s[i][j];
			p[j]=p[j-1]*31;
			v2[i][j]=v2[i][j-1]*61+s[i][j];
			p2[j]=p2[j-1]*61;
		}
	}
	
	int aa=0;
	for(int id=1;id<=m;id++ ){
		int L=i[id],R=j[id];
		int l=1,r=min(s[L].size(),s[R].size()),res=0;
		r--;
		while(l<=r) {
			int mid=l+r>>1;
			if(v[L][mid]==v[R][mid]&&v2[L][mid]==v2[R][mid]) res=mid,l=mid+1;
			else r=mid-1;
		}
		aa+=res;
	}
	cout<<aa;
	return 0;
}
0