結果

問題 No.515 典型LCP
ユーザー lumc_lumc_
提出日時 2018-08-30 22:46:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 4,201 bytes
コンパイル時間 2,143 ms
コンパイル使用メモリ 185,924 KB
実行使用メモリ 15,360 KB
最終ジャッジ日時 2024-09-13 20:36:22
合計ジャッジ時間 4,881 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 AC 106 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 75 ms
6,944 KB
testcase_06 AC 76 ms
6,944 KB
testcase_07 AC 75 ms
6,940 KB
testcase_08 AC 87 ms
6,940 KB
testcase_09 AC 77 ms
6,940 KB
testcase_10 AC 78 ms
6,944 KB
testcase_11 AC 77 ms
6,944 KB
testcase_12 AC 78 ms
6,944 KB
testcase_13 AC 78 ms
6,944 KB
testcase_14 RE -
testcase_15 AC 75 ms
6,944 KB
testcase_16 AC 75 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// #undef DEBUG
// #define DEBUG
/// {{{ DEBUG --- ///
#ifdef DEBUG
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << "{"; for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? ", " : ""); o << "}"; return o; }
#ifdef USE_COUT
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cout<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
#else
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
#endif
template<class T> inline void dump2D(T &d, size_t sizey, size_t sizex) { ostream&o=
#ifdef USE_COUT
  cout;
#else
  cerr;
#endif
  for(size_t i = 0; i < sizey; i++) { for(size_t j = 0; j < sizex; j++) o << d[i][j] << " "; o << endl; }
}
#else
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? " " : ""); return o; }
#define dump(...) (42)
#define dump2D(...) (42)
#endif
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
/// }}}--- ///

// 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));
    t.resize(1);
    t.resize(1, vector<T>());
  }
  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