結果

問題 No.515 典型LCP
コンテスト
ユーザー lumc_
提出日時 2018-08-30 22:49:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 218 ms / 1,000 ms
コード長 2,569 bytes
コンパイル時間 2,004 ms
コンパイル使用メモリ 185,080 KB
実行使用メモリ 15,320 KB
最終ジャッジ日時 2024-09-13 20:36:44
合計ジャッジ時間 4,359 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// NOTE : query in range!
/// --- Sparse Table Library {{{ ///

// struct SemiLattice {
//   using T = _underlying_set_;
//   static T op(T const &a, T const &b) { return _a_op_b_; }
// };

template<class SemiLattice>
struct SparseTable {
  using T = typename SemiLattice::T;
  size_t n;
  vector<size_t> log2;
  vector< vector<T> > t;
  T identity;
  SparseTable():n(0) {}
  SparseTable(size_t n, T identity = T()): n(n), log2(n + 1), identity(identity) {
    for(size_t i = 2; i <= n; i++) log2[i] = log2[i >> 1] + 1;
    t.resize(log2[n] + 1, vector<T>(n, identity));
  }
  template<class InputIter, class = typename iterator_traits<InputIter>::value_type>
    SparseTable(InputIter first, InputIter last, T identity = T())
    : SparseTable(distance(first, last), identity) {
      copy(first, last, begin(t[0]));
      build();
    }
  void set(size_t i, T val) { t[0][i] = val; }
  T get(size_t i) { return t[0][i]; }
  void build() {
    for(size_t j = 0; j < log2[n]; j++) {
      size_t w = 1 << j;
      for(size_t i = 0; i + (w << 1) <= n; i++) {
        t[j + 1][i] = SemiLattice::op(t[j][i], t[j][i + w]);
      }
    }
  }
  T query(size_t l, size_t r) {
    if(r - l < 1) return identity;
    size_t j = log2[r - l];
    return SemiLattice::op(t[j][l], t[j][r - (1 << j)]);
  }
};

/// }}}--- ///

// sparse table expample {{{

struct RMQSL {
  using T = int;
  static T op(T const &a, T const &b) { return a < b ? a : b; }
};

// }}}

ll n;
ll x, d;
pair< int, int > nx() {
  int i = (x / (n - 1)), j = (x % (n - 1));
  if(i > j)
    swap(i, j);
  else
    j++;
  x = (x + d) % (n * (n - 1));
  return make_pair(i, j);
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n;
  vector<string> s(n);
  for(int i = 0; i < n; i++) cin >> s[i];
  vector<int> ord(n);
  iota(begin(ord), end(ord), 0);
  // O(NlogN + sum logN) ?
  sort(begin(ord), end(ord), [&](int a, int b){
      return s[a] < s[b];
      });
  auto id = ord;
  for(int i = 0; i < n; i++) id[ord[i]] = i;
  vector<int> lcp(n-1);
  for(int x = 0; x < n - 1; x++) {
    int i = ord[x];
    int j = ord[x + 1];
    while(lcp[x] < s[i].size() && lcp[x] < s[j].size() &&
        s[i][lcp[x]] == s[j][lcp[x]]) lcp[x]++;
  }
  SparseTable<RMQSL> ecas(begin(lcp), end(lcp), 1e9);
  
  int m;
  cin >> m >> x >> d;
  ll ans = 0;
  while(m--) {
    int i, j;
    tie(i, j) = nx();
    i = id[i];
    j = id[j];
    if(i > j) swap(i, j);
    ans += ecas.query(i, j);
  }
  cout << ans << endl;
  return 0;
}
0