結果

問題 No.515 典型LCP
ユーザー lumc_lumc_
提出日時 2018-08-29 23:47:56
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 5,984 bytes
コンパイル時間 1,819 ms
コンパイル使用メモリ 175,652 KB
実行使用メモリ 40,024 KB
最終ジャッジ日時 2024-09-13 19:42:37
合計ジャッジ時間 6,427 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

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; }
/// }}}--- ///


// Mamber & Mayers
// SA
// *1 : if you want original comparison rule, change here
struct SA {
  const int n;
  const string &s;
  vector< int > rnk;
  vector< int > sa;
  int operator[](int i) const { return sa[i]; }
  SA(const string &s) : n(s.size()), s(s), rnk(n), sa(n) {
    iota(begin(sa), end(sa), 0);
    sort(begin(sa), end(sa), [&](int a, int b) { return s[a] < s[b]; }); // *1
    for(int i = 0; i < n; i++) rnk[i] = s[i];                        // *1
    for(int i = 1; i < n; i <<= 1) {
      auto comp = [&](int a, int b) {
        if(rnk[a] != rnk[b]) return rnk[a] < rnk[b];
        a = a + i < n ? rnk[a + i] : -1;
        b = b + i < n ? rnk[b + i] : -1;
        return a < b;
      };
      sort(begin(sa), end(sa), comp);
      auto tmp = rnk;
      tmp[sa[0]] = 0;
      for(int j = 1; j < n; j++) tmp[sa[j]] = tmp[sa[j - 1]] + comp(sa[j - 1], sa[j]); ///
      rnk = tmp;
    }
  }
};

struct LCP {
  const int n;
  const string &s;
  vector< int > lcp;
  int operator[](int i) const { return lcp[i]; }
  LCP(const SA& sa) : n(sa.n), s(sa.s), lcp(n - 1) {
    int h = 0;
    for(int i = 0; i < n - 1; i++) {
      int j = sa[sa.rnk[i] - 1];
      if(h) h--;
      while(i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
      lcp[sa.rnk[i] - 1] = h;
    }
  }
};

// NOTE : query in range!
/// --- SegmentTree Library {{{ ///

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

template<class Monoid>
struct SegTree {
private:
  using T = typename Monoid::T;
  int n;
  std::vector<T> data;
  // call after touch data[i]
  void prop(int i) { data[i] = Monoid::op(data[2 * i], data[2 * i + 1]); }
public:
  SegTree(): n(0) {}
  SegTree(int n): n(n) {
    data.resize(n * 2, Monoid::identity());
  }
  template<class InputIter, class = typename std::iterator_traits<InputIter>::value_type>
    SegTree(InputIter first, InputIter last)
    : SegTree(std::distance(first, last)) {
      copy(first, last, std::begin(data) + n);
      // fill from deep
      for(int i = n - 1; i > 0; i--) prop(i);
    }
  void set(int i, const T& v) {
    data[i += n] = v;
    while(i >>= 1) prop(i); // propUp
  }
  T get(int i) { return data[i + n]; }
  T query(int l, int r) {
    T tmpL = Monoid::identity(), tmpR = Monoid::identity();
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) tmpL = Monoid::op(tmpL, data[l++]);
      if(r & 1) tmpR = Monoid::op(data[--r], tmpR);
    }
    return Monoid::op(tmpL, tmpR);
  }
  inline void dum(int r = -1) {
#ifdef DEBUG
    std::ostream & o =
#ifdef USE_COUT
      std::cout
#else
      std::cerr
#endif
      ;
    if(r < 0) r = n;
    o << "{";
    for(int i = 0; i < std::min(r, n); i++) o << (i ? ", " : "") << get(i);
    o << "}" << std::endl;
#endif
  }
};

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

// Monoid examples {{{

constexpr long long inf = std::numeric_limits<long long>::max();
// using P = pair<ll, ll>

struct MonoidMin {
  using T = long long;
  static T op(const T& a, const T& b) { return std::min(a, b); }
  static constexpr T identity() { return inf; }
};
struct MonoidSum {
  using T = long long;
  static T op(const T& a, const T& b) { return a + b; }
  static constexpr T identity() { return 0; }
};
struct MonoidMax {
  using T = long long;
  static T op(const T& a, const T& b) { return std::max(a, b); }
  static constexpr T identity() { return -inf; }
};

// }}}

using RMQ = SegTree<MonoidMin>;

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;
  string s;
  vector<int> idx(n);
  vector<int> len(n);
  for(int i = 0; i < n; i++) {
    string t;
    cin >> t;
    idx[i] = s.size();
    len[i] = t.size();
    s += t + "-";
  }
  SA sa(s);
  LCP lcp(sa);
  RMQ ecas(begin(lcp.lcp), end(lcp.lcp));

  int m;
  cin >> m >> x >> d;
  ll ans = 0;
  while(m--) {
    int i, j;
    tie(i, j) = nx();
    int a = min(len[i], len[j]);
    i = idx[i];
    j = idx[j];
    i = sa.rnk[i];
    j = sa.rnk[j];
    a = min(a, (int) ecas.query(min(i,j), max(i,j)));
    ans += a;
  }
  cout << ans << endl;
  return 0;
}
0