結果
| 問題 | No.515 典型LCP |
| ユーザー |
 coindarw
|
| 提出日時 | 2023-04-26 22:56:47 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 827 ms / 1,000 ms |
| コード長 | 10,387 bytes |
| コンパイル時間 | 4,673 ms |
| コンパイル使用メモリ | 272,848 KB |
| 実行使用メモリ | 32,608 KB |
| 最終ジャッジ日時 | 2024-11-16 06:57:59 |
| 合計ジャッジ時間 | 12,288 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 827 ms
32,608 KB |
| testcase_01 | AC | 689 ms
26,520 KB |
| testcase_02 | AC | 402 ms
21,760 KB |
| testcase_03 | AC | 1 ms
6,820 KB |
| testcase_04 | AC | 2 ms
6,816 KB |
| testcase_05 | AC | 451 ms
31,792 KB |
| testcase_06 | AC | 639 ms
31,472 KB |
| testcase_07 | AC | 573 ms
31,912 KB |
| testcase_08 | AC | 673 ms
31,320 KB |
| testcase_09 | AC | 334 ms
21,832 KB |
| testcase_10 | AC | 329 ms
21,740 KB |
| testcase_11 | AC | 325 ms
21,768 KB |
| testcase_12 | AC | 333 ms
21,680 KB |
| testcase_13 | AC | 266 ms
21,692 KB |
| testcase_14 | AC | 51 ms
21,856 KB |
| testcase_15 | AC | 296 ms
31,360 KB |
| testcase_16 | AC | 285 ms
31,500 KB |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using ll = long long;
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); ++i)
constexpr int inf = 2000'000'000;
constexpr ll linf = 4000000000000000000ll;
constexpr ll M7 = 1000000007ll;
constexpr ll M09 = 1000000009ll;
constexpr ll M9 = 998244353ll;
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using namespace atcoder;
template <typename T>
inline ostream& operator<<(ostream& os, vector<T>& v) {
for (auto& e : v) os << e << " ";
return os;
}
template <typename T, typename U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) noexcept {
return os << "(" << p.first << ", " << p.second << ")";
}
#ifdef ONLINE_JUDGE
#define debug(...)
#else
#define debug(...) cerr << "<" << #__VA_ARGS__ << ">: ", debug_out(__VA_ARGS__)
template <typename T>
void debug_out(T t) {
cerr << t << endl;
}
template <typename T, typename... Args>
void debug_out(T t, Args... args) {
cerr << t << ", ";
debug_out(args...);
}
#endif
class StrAlgos {
private:
public:
static vector<int> sa_is(vector<int> v, int upper) {
// 1 <= v[i] <= upper
if (v.size() == 0)
return {};
else if (v.size() == 1)
return {0};
else if (v.size() == 2)
if (v[0] < v[1])
return {0, 1};
else
return {1, 0};
constexpr int TERM = 0;
v.emplace_back(TERM);
const int n = v.size();
vector<int> bl(upper + 1), br(upper + 1); // bucket range
for (int i = 0; i < n; ++i) br[v[i]]++;
for (int i = 1; i <= upper; ++i) br[i] += br[i - 1];
for (int i = 1; i <= upper; ++i) bl[i] = br[i - 1];
vector<bool> is_l(n);
vector<int> lms, sa(n, -1), lms_ord(n); // lms_ord[i] := 0 -> not lms, 1~ -> 1-indexed
for (int i = n - 2; i >= 0; --i) is_l[i] = (v[i] == v[i + 1]) ? is_l[i + 1] : (v[i] > v[i + 1]);
for (int i = 1; i < n; ++i) {
if (!is_l[i] && is_l[i - 1]) {
sa[--br[v[i]]] = i;
lms_ord[i] = ~int(lms.size());
lms.emplace_back(i);
}
}
for (int i = 0; i < upper; ++i) br[i] = bl[i + 1];
br[upper] = n;
for (int i = 0; i < n; ++i)
if (sa[i] > 0 && is_l[sa[i] - 1])
sa[bl[v[sa[i] - 1]]++] = sa[i] - 1;
for (int i = 1; i <= upper; ++i) bl[i] = br[i - 1];
for (int i = 1; i < n; i++)
if (sa[i] > -1 && !is_l[sa[i]])
sa[i] = -1;
for (int i = n - 1; i >= 1; i--)
if (sa[i] > 0 && !is_l[sa[i] - 1])
sa[--br[v[sa[i] - 1]]] = sa[i] - 1;
for (int i = 0; i < upper; ++i) br[i] = bl[i + 1];
br[upper] = n;
vector<int> lms_substr_sorted(lms.size());
int cnt = 0;
for (int i = 0; i < n; ++i)
if (sa[i] > -1 && lms_ord[sa[i]])
lms_substr_sorted[cnt++] = sa[i];
// same lms_substr -> same rank
auto same = [&](int l1, int l2) {
if (l1 > l2)
swap(l1, l2);
if (l2 == n - 1)
return false;
int p1 = l1, p2 = l2;
while (p1 <= lms[~lms_ord[l1] + 1] && p2 < n)
if (v[p1] == v[p2])
++p1, ++p2;
else
return false;
return true;
};
vector<int> ord(lms.size());
ord[0] = 1;
for (int i = 0; i < lms.size() - 1; ++i)
ord[i + 1] = same(lms_substr_sorted[i], lms_substr_sorted[i + 1]) ? ord[i] : (ord[i] + 1);
vector<int> va(lms.size()); // make array of appearance order
for (int i = 0; i < lms.size(); ++i) va[~lms_ord[lms_substr_sorted[i]]] = ord[i];
auto lms_sorted = sa_is(va, ord.back());
// place lms at correct position
fill(all(sa), -1);
for (int i = lms.size() - 1; i >= 0; i--) sa[--br[v[lms[lms_sorted[i]]]]] = lms[lms_sorted[i]];
for (int i = 0; i < upper; ++i) br[i] = bl[i + 1];
br[upper] = n;
for (int i = 0; i < n; ++i)
if (sa[i] > 0 && is_l[sa[i] - 1])
sa[bl[v[sa[i] - 1]]++] = sa[i] - 1;
for (int i = 1; i < n; i++)
if (sa[i] > -1 && !is_l[sa[i]])
sa[i] = -1;
for (int i = n - 1; i >= 1; i--)
if (sa[i] > 0 && !is_l[sa[i] - 1])
sa[--br[v[sa[i] - 1]]] = sa[i] - 1;
sa.erase(sa.begin());
return sa;
}
static vector<int> sa_is(vector<int> v) {
auto cv = v;
sort(all(cv));
cv.erase(unique(all(cv)), cv.end());
for (auto& e : v) e = lower_bound(all(cv), e) - cv.begin();
return sa_is(v, cv.size() - 1);
}
static vector<int> sa_is(string s) {
vector<int> v(s.size());
for (int i = 0; i < s.size(); i++) v[i] = s[i];
return sa_is(v, 255);
}
static vector<int> lcp(const string& s, const vector<int>& sa) {
assert(sa.size() == s.size());
vector<int> rank(s.size()), _lcp(s.size() - 1);
const int n = s.size();
for (int i = 0; i < n; i++) rank[sa[i]] = i;
int h = 0;
for (int i = 0; i < n; i++) {
if (rank[i] == 0)
continue;
int j = sa[rank[i] - 1];
if (h > 0)
h--;
for (; j + h < n && i + h < n; h++)
if (s[j + h] != s[i + h])
break;
_lcp[rank[i] - 1] = h;
}
return _lcp;
}
static vector<int> lcp(const vector<int>& s, const vector<int>& sa) {
assert(sa.size() == s.size());
const int n = s.size();
vector<int> rank(n), _lcp(n - 1);
for (int i = 0; i < n; i++) rank[sa[i]] = i;
int h = 0;
for (int i = 0; i < n; i++) {
if (rank[i] == 0)
continue;
int j = sa[rank[i] - 1];
if (h > 0)
h--;
for (; j + h < n && i + h < n; h++)
if (s[j + h] != s[i + h])
break;
_lcp[rank[i] - 1] = h;
}
return _lcp;
}
static vector<int> z_algo(string s) {
int n = s.size();
vector<int> v(n);
v[0] = n;
int l = -1, r = -1;
reps(i, n - 1) {
if (l != -1)
v[i] = max(min(v[i - l], int(r - i)), 0);
while (i + v[i] < n && s[v[i]] == s[i + v[i]]) v[i]++;
if (i + v[i] > r) {
l = i;
r = i + v[i];
}
}
return v;
}
static vector<int> z_algo(vector<int> v) {
int n = v.size();
vector<int> res(n);
res[0] = n;
int l = -1, r = -1;
reps(i, n - 1) {
if (l != -1)
res[i] = max(0, min(int(r - i), res[i - l]));
while (i + res[i] < n && v[res[i]] == v[i + res[i]]) res[i]++;
if (i + res[i] > r) {
l = i;
r = i + res[i];
}
}
return res;
}
};
template <typename T, T (*op)(T, T), T (*e)()>
class SegTree {
private:
int n, _n;
std::vector<T> dat;
T _query(int a, int b, int p, int l, int r) {
if (a >= r || b <= l) {
return e();
} else if (a <= l && r <= b) {
return dat.at(p);
}
int mid = (l + r) / 2;
return op(_query(a, b, p * 2 + 1, l, mid), _query(a, b, p * 2 + 2, mid, r));
}
public:
SegTree(int n) : SegTree(std::vector<T>(n, e())) {}
SegTree(const std::vector<T>& v) : _n(int(v.size())) {
this->n = 1;
while (this->n < _n) {
this->n *= 2;
}
dat = std::vector<T>(2 * this->n - 1);
for (int i = 0; i < _n; i++) {
dat.at(i + n - 1) = v.at(i);
}
for (int i = n - 2; i >= 0; i--) {
dat.at(i) = op(dat.at(i * 2 + 1), dat.at(i * 2 + 2));
}
}
T query(int l, int r) {
assert(0 <= l && l < r && r <= _n);
if (l == r)
return e();
return _query(l, r, 0, 0, n);
}
void set(int p, T a) {
assert(0 <= p && p < _n);
p += n - 1;
dat.at(p) = a;
while (p > 0) {
p = (p - 1) / 2;
dat.at(p) = op(dat.at(p * 2 + 1), dat.at(p * 2 + 2));
}
}
T get(int p) {
assert(0 <= p && p < _n);
return dat.at(p + n - 1);
}
void print() {
int lf = 0;
rep(i, 2 * n - 1) {
// cerr << "(" << dat[i].first.first << ", " << dat[i].first.second << ", "
// << dat[i].second << ")\t";
cerr << "(" << dat[i] << ")\t";
if (i == lf) {
lf = lf * 2 + 2;
cerr << endl;
}
}
}
};
int e() {
return inf;
}
int op(int a, int b) {
return min(a, b);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin >> n;
vector<int> a(n);
string s;
int sum = 0;
rep(i, n) {
string t;
cin >> t;
a[i] = sum;
sum += t.size();
s += t;
}
auto sa = StrAlgos::sa_is(s);
auto lcp = StrAlgos::lcp(s, sa);
segtree<int, op, e> st(lcp);
vector<int> rev(n);
rep(i, sum) {
auto lb = lower_bound(all(a), sa[i]);
if (lb != a.end() && *lb == sa[i])
rev.at(lb - a.begin()) = i;
}
a.push_back(sum);
ll m, x, d;
cin >> m >> x >> d;
ll ans = 0;
reps(k, m) {
ll i = (x / (n - 1)) + 1;
ll j = (x % (n - 1)) + 1;
if (i > j)
swap(i, j);
else
j++;
int _i = rev[i - 1], _j = rev[j - 1];
if (_i > _j)
swap(_i, _j);
ll r = min({st.prod(_i, _j), a[i] - a[i - 1], a[j] - a[j - 1]});
ans += r;
x = (x + d) % (n * (n - 1));
}
cout << ans << "\n";
return 0;
}