結果

問題 No.515 典型LCP
ユーザー r_dream0r_dream0
提出日時 2017-05-08 12:18:15
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,169 bytes
コンパイル時間 1,420 ms
コンパイル使用メモリ 86,408 KB
実行使用メモリ 8,960 KB
最終ジャッジ日時 2024-09-14 17:17:06
合計ジャッジ時間 13,291 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 AC 841 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 302 ms
5,376 KB
testcase_06 AC 504 ms
5,376 KB
testcase_07 AC 391 ms
5,376 KB
testcase_08 AC 566 ms
5,376 KB
testcase_09 AC 521 ms
5,376 KB
testcase_10 AC 740 ms
5,376 KB
testcase_11 AC 739 ms
5,376 KB
testcase_12 AC 741 ms
5,376 KB
testcase_13 AC 422 ms
5,376 KB
testcase_14 AC 27 ms
5,376 KB
testcase_15 AC 161 ms
5,376 KB
testcase_16 AC 176 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <climits>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

#define REP(i,x) for(int i = 0; i < (int)(x); i++)

// LCPを計算する O(N)
vector<int> build_lcp(const string &s, vector<int> sa){
  int n = s.size(), h = 0;
  vector<int> rank(n + 1), lcp(n + 1);
  REP(i, n + 1) rank[sa[i]] = i;
  REP(i, n){
    int j = sa[rank[i] - 1];

    if(h > 0) h--;
    for(; j + h < n && i + h < n; h++){
      if(s[j + h] != s[i + h])break;
    }

    lcp[rank[i] -1] = h;
  }
  return lcp;
}
class RMQ{
  private:
    vector<int> val;
    int n;
  public:
    RMQ(int size){
      n=1;
      while(n<size)n<<=1;
      val=vector<int>(2*n,INT_MAX);
    }
    //x番目の要素をaに更新する
    void update(int x,int a){
      x+=n-1;
      val[x]=a;
      while(x>0){
        x=(x-1)/2;
        val[x]=min(val[x*2+1],val[x*2+2]);
      }
    }
    //a<=x<b
    int minimum(int a,int b,int k=0,int l=0,int r=-1){
      if(r==-1)r=n;
      if(r<=a||b<=l)return INT_MAX;
      if(a<=l&&r<=b){
        return val[k];
      }else{
        return min(minimum(a,b,k*2+1,l,(l+r)/2),minimum(a,b,k*2+2,(l+r)/2,r));
      }
    }
};

int main() {
  int N;
  cin >> N;
  vector<int> inv(N);
  vector<pair<string, int> > s(N);
  for(int i = 0; i < N; i++) {
    cin >> s[i].first;
    s[i].second = i;
  }
  sort(s.begin(), s.end());
  for(int i = 0; i < N; i++) {
    inv[s[i].second] = i;
  }
  vector<int> lcp(N - 1);
  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]) lcp[i] = j + 1; else break;
    }
  }
  RMQ rmq(N - 1);
  for(int i = 0; i < N - 1; i++) {
    rmq.update(i, lcp[i]);
  }
  int M;
  cin >> M;
  int64_t x, d;
  cin >> x >> d;
  int64_t answer = 0;
  for(int i = 0; i < M; i++) {
    int64_t ii = x / (N - 1);
    int64_t jj = x % (N - 1);
    if(ii > jj) {
      swap(ii, jj);
    } else {
      jj++;
    }
    int ipos = inv[ii];
    int jpos = inv[jj];
    if(ipos > jpos) swap(ipos, jpos);
    answer += rmq.minimum(ipos, jpos);
    x = (x + d) % (N * (N - 1));
  }
  cout << answer << endl;
}
0