結果

問題 No.515 典型LCP
ユーザー nohtaraynohtaray
提出日時 2019-10-05 14:10:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 402 ms / 1,000 ms
コード長 4,323 bytes
コンパイル時間 7,581 ms
コンパイル使用メモリ 392,120 KB
実行使用メモリ 100,060 KB
最終ジャッジ日時 2024-10-05 20:29:21
合計ジャッジ時間 11,987 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 402 ms
99,932 KB
testcase_01 AC 398 ms
100,060 KB
testcase_02 AC 145 ms
70,096 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 119 ms
69,964 KB
testcase_06 AC 122 ms
69,964 KB
testcase_07 AC 121 ms
69,968 KB
testcase_08 AC 135 ms
69,836 KB
testcase_09 AC 122 ms
70,240 KB
testcase_10 AC 129 ms
69,996 KB
testcase_11 AC 131 ms
70,128 KB
testcase_12 AC 131 ms
69,868 KB
testcase_13 AC 130 ms
69,968 KB
testcase_14 AC 7 ms
5,248 KB
testcase_15 AC 120 ms
70,044 KB
testcase_16 AC 121 ms
70,044 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <boost/format.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/optional.hpp>

#ifdef DEBUG
#include "libs/debug.cpp"
#define DEBUG 1
#else
#define DEBUG 0
#endif

#define rep(i, n) repr((i), 0, (n))
#define repr(i, a, t) reps((i), (a), (t), 1)
#define reps(i, a, t, s) for (long long (i) = (a); (i) < (long long)(t); (i) += (s))
#define rrep(i, n) rrepr((i), (n) - 1, 0)
#define rrepr(i, a, t) rreps((i), (a), (t), 1)
#define rreps(i, a, t, s) for (long long (i) = (a); (i) >= (long long)(t); (i) -= (s))
#define each(v, c) for (auto &&(v) : (c))
#define all(c) (c).begin(), (c).end()

using namespace std;
namespace mp = boost::multiprecision;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using ml = mp::cpp_int;
template<typename T>
using optional = boost::optional<T>;
const auto none = boost::none;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;

/**
 * 構築 O(NlogN)、クエリ O(1)
 * @tparam T
 */
template<typename T>
class SparseTable {
 private:
  vector<T> values;
  vector<vector<unsigned long>> table;
  vector<unsigned long> msb;
  function<T(T, T)> fn;

  static vector<vector<unsigned long >> build(const vector<T> &values, function<T(T, T)> fn) {
    unsigned long size = (unsigned long) log2(values.size()) + 1;

    vector<vector<unsigned long >> st(values.size(), vector<unsigned long>(size));
    for (unsigned long i = 0; i < values.size(); ++i) st[i][0] = i;
    for (unsigned long p = 1; p < size; ++p) {
      for (unsigned long i = 0; i < values.size(); ++i) {
        unsigned long q = min(i + (1 << (p - 1)), (unsigned long) values.size() - 1);
        unsigned long l = st[i][p - 1];
        unsigned long r = st[q][p - 1];
        if (values[l] == fn(values[l], values[r])) {
          st[i][p] = l;
        } else {
          st[i][p] = r;
        }
      }
    }
    return st;
  }

 public:
  SparseTable(const vector<T> &values, function<T(T, T)> fn) {
    this->values = values;
    this->fn = fn;

    // table[i][p]: [i, i + 2^p) に fn を適用した結果の値のインデックス
    table = build(values, fn);

    // msb[i]: 最上位ビット; どの p を見るべきか
    msb = vector<unsigned long>(values.size() + 1);
    for (unsigned long i = 2; i < values.size() + 1; ++i) {
      msb[i] = msb[i >> 1] + 1;
    }
  }

  /**
   * [a, b) に fn を適用した結果
   */
  T get(unsigned long a, unsigned long b) {
    if (b <= a) throw invalid_argument("a < b でないといけません");
    if (b > values.size()) throw invalid_argument("範囲外です");
    unsigned long p = msb[b - a];
    return fn(values[table[a][p]], values[table[b - (1 << p)][p]]);
  }
};

template<typename T>
vector<unsigned long> argsort(const vector<T> &vec) {
  vector<pair<T, unsigned long>> values;
  vector<unsigned long> ret;

  for (unsigned long i = 0; i < vec.size(); ++i) values.emplace_back(vec[i], i);
  sort(values.begin(), values.end());
  for (const auto &item: values) ret.push_back(item.second);
  return ret;
}

vector<pair<ll, ll>> genq(ll N, ll M, ll X, ll D) {
  vector<pair<ll, ll>> ret;
  repr (k, 1, M + 1) {
    ll i, j;
    i = (X / (N - 1)) + 1;
    j = (X % (N - 1)) + 1;
    if (i > j) swap(i, j);
    else j++;
    ret.emplace_back(i, j);
    X = (X + D) % (N * (N - 1));
  }
  return ret;
}

int main() {
  cout << fixed << setprecision(10);
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ifstream ifs;
  if (DEBUG) {
    ifs.open("src/_in.txt");
    cin.rdbuf(ifs.rdbuf());
  }

  ll N;
  cin >> N;
  vector<string> S;
  rep (i, N) {
    string v0;
    cin >> v0;
    S.push_back(v0);
  }
  ll M, X, D;
  cin >> M >> X >> D;

  auto idx = argsort(argsort(S));
  sort(all(S));

  // lcp[i]: S[i] と S[i + 1] の共通接頭辞の長さ
  vector<ll> lcp(N - 1);
  rep (i, N - 1) {
    ll j = 0;
    while (j < S[i].size() && j < S[i + 1].size() && S[i][j] == S[i + 1][j]) ++j;
    lcp[i] = j;
  }

  auto st = SparseTable<ll>(lcp, [](ll a, ll b) { return min(a, b); });

  ll ans = 0;
  auto queries = genq(N, M, X, D);
  each (query, queries) {
    ll i, j;
    tie(i, j) = query;
    i = idx[i - 1];
    j = idx[j - 1];
    if (i > j) swap(i, j);
    ans += st.get(i, j);
  }
  cout << ans << "\n";
}
0