結果

問題 No.515 典型LCP
ユーザー ixmelixmel
提出日時 2017-05-06 12:43:50
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 410 ms / 1,000 ms
コード長 2,597 bytes
コンパイル時間 1,230 ms
コンパイル使用メモリ 100,888 KB
実行使用メモリ 18,816 KB
最終ジャッジ日時 2024-09-14 13:50:39
合計ジャッジ時間 4,369 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 399 ms
18,816 KB
testcase_01 AC 410 ms
18,688 KB
testcase_02 AC 135 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 87 ms
5,376 KB
testcase_06 AC 88 ms
5,376 KB
testcase_07 AC 88 ms
5,376 KB
testcase_08 AC 121 ms
5,376 KB
testcase_09 AC 90 ms
5,376 KB
testcase_10 AC 92 ms
5,376 KB
testcase_11 AC 91 ms
5,376 KB
testcase_12 AC 92 ms
5,376 KB
testcase_13 AC 91 ms
5,376 KB
testcase_14 AC 18 ms
5,376 KB
testcase_15 AC 87 ms
5,376 KB
testcase_16 AC 88 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mt make_tuple
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<string,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e9;
const ll INF=2e18;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
//http://tookunn.hatenablog.com/entry/2016/07/13/211148
//
//make:O(NlogN) update:muri query:O(1)
//
typedef int SegT;
const int defvalue=0;
class ST{//Sparse_table
	public:
		vector<SegT> A,log_table;
		vector<vector<SegT> >table;
		int n;
		SegT combine(SegT a,SegT b){return min(a,b);}
		ST(const vector<SegT> &in){
			n=in.size();
			A=in;
			log_table=vector<SegT>(n+1);
			loop(i,2,n+1)log_table[i]=log_table[i>>1]+1;
			table=vector<vector<SegT> >(n,vector<SegT>(log_table[n]+1));
			rep(i,n)table[i][0]=i;
			for(int k=1;(1<<k)<=n;k++){
				for(int i=0;i+(1<<k)<=n;i++){
					int first=table[i][k-1];
					int second=table[i+(1<<(k-1))][k-1];
					if(A[first]<A[second])table[i][k]=first;
					else table[i][k]=second;
				}
			}
		}
		SegT query(int s,int t){//[a,b] 0-index
			if(s>t)assert(1);
			int d=t-s+1;
			int k=log_table[d];
			int out;
			if(A[table[s][k]]<A[table[t-(1<<k)+1][k]])
				out=table[s][k];
			else out=table[t-(1<<k)+1][k];
//			return out;
			return A[out];
		}
		void tmp(){
			rep(i,n){
				rep(j,log_table[n]+1)cout<<" "<<table[i][j];
				cout<<endl;
			}
		}
};
int main(){
	ll n;
	cin>>n;
	vp in(n);
	rep(i,n)cin>>in[i].first;
	rep(i,n)in[i].second=i;
	sort(all(in));
	vi lcp(n-1);
	rep(i,n-1){
		int co=0;
		rep(j,min(in[i].first.size(),in[i+1].first.size()))if(in[i].first[j]==in[i+1].first[j])co++;else break;
		lcp[i]=co;
	}
	ST st(lcp);
	ll m,x,d;
	cin>>m>>x>>d;
	vi to(n);
	rep(i,n)to[in[i].second]=i;
	ll out=0;
	while(m--){
		int i=x/(n-1);
		int j=x%(n-1);
		if(i>j)swap(i,j);
		else j++;
		i=to[i];j=to[j];
		if(i>j)swap(i,j);
		x=(x+d)%(n*(n-1));
		out+=st.query(i,j-1);
	}
	cout<<out<<endl;
}
0