結果
問題 | No.515 典型LCP |
ユーザー | ciel |
提出日時 | 2017-05-06 16:38:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,508 bytes |
コンパイル時間 | 2,205 ms |
コンパイル使用メモリ | 104,956 KB |
実行使用メモリ | 8,584 KB |
最終ジャッジ日時 | 2023-10-12 15:08:43 |
合計ジャッジ時間 | 13,720 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | TLE | - |
testcase_02 | AC | 870 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 263 ms
4,348 KB |
testcase_06 | AC | 452 ms
4,352 KB |
testcase_07 | AC | 278 ms
4,392 KB |
testcase_08 | AC | 536 ms
4,348 KB |
testcase_09 | AC | 469 ms
4,348 KB |
testcase_10 | AC | 762 ms
4,348 KB |
testcase_11 | AC | 762 ms
4,348 KB |
testcase_12 | AC | 762 ms
4,352 KB |
testcase_13 | AC | 385 ms
4,348 KB |
testcase_14 | AC | 12 ms
4,352 KB |
testcase_15 | AC | 161 ms
4,356 KB |
testcase_16 | AC | 150 ms
4,352 KB |
ソースコード
#pragma GCC optimize("O3") #pragma GCC target("avx") #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; #define INF (1<<29) class RMQ{ int size; vector<int> minval; int _query(int a,int b,int k,int l, int r){ if(r<=a||b<=l)return INF; if(a<=l&&r<=b)return minval[k]; else{ int vl=_query(a,b,k*2+1,l,(l+r)/2); int vr=_query(a,b,k*2+2,(l+r)/2,r); return min(vl,vr); } } public: RMQ(int k){init(k);} void init(int k){ for(size=1;size<k;)size<<=1; //size=1<<(32-__builtin_clz(k)); minval=vector<int>(2*size-1,INF); } void update(int k,int t){ k+=size-1; minval[k]=t; while(k>0){ k=(k-1)/2; minval[k]=min(minval[k*2+1],minval[k*2+2]); } } int query(int a,int b){ return _query(a,b,0,0,size); } }; int N,I,J; long long X,D; void iterate(){ I=X/~-N; J=X%~-N; if(I>J)swap(I,J); else J++; X=(X+D)%((long long)N*~-N); } int calc(const string &s,const string &t){ int l=min(s.size(),t.size()),i=0; for(;i<l&&s[i]==t[i];i++); return i; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int M; long long R=0; cin>>N; vector<pair<string,int>>v(N); vector<int>rev(N); for(int i=0;i<N;i++)cin>>v[i].first,v[i].second=i; cin>>M>>X>>D; sort(v.begin(),v.end()); for(int i=0;i<N;i++)rev[v[i].second]=i; RMQ rmq(N); for(int i=0;i<N-1;i++)rmq.update(i+1,calc(v[i].first,v[i+1].first)); for(;M--;){ iterate(); int i=rev[I],j=rev[J]; if(i>j)swap(i,j); R+=rmq.query(i+1,j+1); } cout<<R<<endl; }