結果

問題 No.515 典型LCP
ユーザー r_dream0r_dream0
提出日時 2017-05-05 22:54:45
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,169 bytes
コンパイル時間 1,093 ms
コンパイル使用メモリ 85,216 KB
実行使用メモリ 8,912 KB
最終ジャッジ日時 2023-10-12 11:03:18
合計ジャッジ時間 12,389 ms
ジャッジサーバーID
(参考情報)
judge13 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 AC 809 ms
4,348 KB
testcase_03 AC 2 ms
4,352 KB
testcase_04 AC 1 ms
4,372 KB
testcase_05 AC 293 ms
4,652 KB
testcase_06 AC 485 ms
4,428 KB
testcase_07 AC 383 ms
4,364 KB
testcase_08 AC 553 ms
4,348 KB
testcase_09 AC 504 ms
4,988 KB
testcase_10 AC 715 ms
5,024 KB
testcase_11 AC 717 ms
5,120 KB
testcase_12 AC 713 ms
4,944 KB
testcase_13 AC 408 ms
4,352 KB
testcase_14 AC 24 ms
4,348 KB
testcase_15 AC 159 ms
4,348 KB
testcase_16 AC 171 ms
4,352 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