結果
問題 | No.515 典型LCP |
ユーザー | pekempey |
提出日時 | 2017-09-13 17:54:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 522 ms / 1,000 ms |
コード長 | 3,879 bytes |
コンパイル時間 | 3,186 ms |
コンパイル使用メモリ | 217,044 KB |
実行使用メモリ | 88,888 KB |
最終ジャッジ日時 | 2024-11-07 19:56:53 |
合計ジャッジ時間 | 8,529 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 522 ms
88,888 KB |
testcase_01 | AC | 366 ms
88,744 KB |
testcase_02 | AC | 217 ms
84,672 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 244 ms
88,244 KB |
testcase_06 | AC | 251 ms
88,120 KB |
testcase_07 | AC | 247 ms
88,112 KB |
testcase_08 | AC | 268 ms
88,236 KB |
testcase_09 | AC | 170 ms
84,648 KB |
testcase_10 | AC | 173 ms
84,772 KB |
testcase_11 | AC | 170 ms
84,524 KB |
testcase_12 | AC | 172 ms
84,652 KB |
testcase_13 | AC | 174 ms
84,772 KB |
testcase_14 | AC | 120 ms
84,660 KB |
testcase_15 | AC | 239 ms
88,172 KB |
testcase_16 | AC | 237 ms
88,060 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; class SuffixDataStructure { public: // a[i]>=0 SuffixDataStructure(const std::vector<int> &a) : a(a) { sa = suffix_array(a); sa.insert(sa.begin(), a.size()); build_lcp(); build_rmq(); } int get_lcp(int i, int j) { if (i == j) { return a.size() - std::max(i, j); } i = isa[i]; j = isa[j]; if (i > j) { std::swap(i, j); } int k = __lg(j - i); return std::min(rmq[k][i], rmq[k][j - (1 << k)]); } private: const std::vector<int> &a; std::vector<int> sa; std::vector<int> isa; std::vector<int> lcp; std::vector<int> lg; std::vector<std::vector<int>> rmq; vector<int> suffix_array(vector<int> a) { const int n = a.size(); if (n == 0) return {}; const int H = *max_element(begin(a), end(a)) + 1; vector<bool> s(n); vector<int> next(n), ss; for (int i = n - 2; i >= 0; i--) { s[i] = a[i] == a[i + 1] ? s[i + 1] : a[i] < a[i + 1]; if (!s[i] && s[i + 1]) ss.push_back(i + 1); } reverse(ss.begin(), ss.end()); for (int i = 0; i < ss.size(); i++) { next[ss[i]] = i + 1 < ss.size() ? ss[i + 1] : n; } auto induced_sort = [&]() { vector<int> sa(n, -1), L(H + 1); for (int i = 0; i < n; i++) L[a[i] + 1]++; for (int i = 0; i < H; i++) L[i + 1] += L[i]; auto S = L; for (int i = (int)ss.size() - 1; i >= 0; i--) { int j = ss[i]; sa[--S[a[j] + 1]] = j; } S = L; sa[L[a[n - 1]]++] = n - 1; for (int i = 0; i < n; i++) { int j = sa[i] - 1; if (j >= 0 && !s[j]) sa[L[a[j]]++] = j; } for (int i = n - 1; i >= 0; i--) { int j = sa[i] - 1; if (j >= 0 && s[j]) sa[--S[a[j] + 1]] = j; } return sa; }; vector<int> rank(n); int j = -1; for (int i : induced_sort()) { if (0 < i && s[i] && !s[i - 1]) { if (j != -1) rank[i] = rank[j] + (next[i] - i != next[j] - j || !equal(a.begin() + i, a.begin() + next[i], a.begin() + j)); j = i; } } vector<int> b; for (int i : ss) b.push_back(rank[i]); vector<int> tmp(ss); ss.clear(); for (int i : suffix_array(b)) ss.push_back(tmp[i]); return induced_sort(); } void build_lcp() { const int n = a.size(); isa.resize(n + 1); lcp.assign(n + 1, 0); for (int i = 0; i <= n; i++) { isa[sa[i]] = i; } int k = 0; for (int i = 0; i < n; i++) { int j = sa[isa[i] - 1]; k = std::max(0, k - 1); while (i + k < n && j + k < n && a[i + k] == a[j + k]) { k++; } lcp[isa[i] - 1] = k; } } void build_rmq() { const int n = lcp.size(); lg.resize(n + 1); for (int i = 2; i <= n; i++) { lg[i] = lg[i / 2] + 1; } const int m = lg[n]; rmq.assign(m + 1, std::vector<int>(n)); for (int i = 0; i < n; i++) { rmq[0][i] = lcp[i]; } for (int i = 0; i < m; i++) { for (int j = 0; j + (1 << i) < n; j++) { rmq[i + 1][j] = std::min(rmq[i][j], rmq[i][j + (1 << i)]); } } } }; int main() { int n; cin >> n; std::vector<int> start(n); std::vector<int> t; std::vector<int> len(n); for (int i = 0; i < n; i++) { start[i] = t.size(); static char buf[800001]; scanf("%s", buf); int j; for (j = 0; buf[j] != 0; j++) { t.push_back(buf[j]); } len[i] = j; } SuffixDataStructure suf(t); int m; long long x, d; cin >> m >> x >> d; long long ans = 0; const long long N = 1LL * n * (n - 1); while (m--) { int i = x / (n - 1); int j = x % (n - 1); if (i > j) { std::swap(i, j); } else { j = j + 1; } x += d; if (x >= N) { x -= N; } ans += min(suf.get_lcp(start[i], start[j]), min(len[i], len[j])); } std::cout << ans << std::endl; }