結果
| 問題 | No.515 典型LCP |
| ユーザー |
 tokusakurai
|
| 提出日時 | 2020-07-14 13:26:22 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,674 bytes |
| コンパイル時間 | 3,157 ms |
| コンパイル使用メモリ | 215,520 KB |
| 実行使用メモリ | 231,584 KB |
| 最終ジャッジ日時 | 2024-11-17 08:58:58 |
| 合計ジャッジ時間 | 35,724 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};
struct Suffix_Array{
const string s;
const int n, log_n, m;
vector<vector<int>> sa, ord;
int log_2(int k){
int ret = 0;
while((1<<ret) < k) ret++;
return ret;
}
Suffix_Array(const string &str) : s(str+'$'), n(sz(s)), log_n(log_2(n)), m(max(n, 256)){
sa.assign(n, vector<int>(log_n+1));
ord.assign(n, vector<int>(log_n+1));
vector<int> cnt(m, 0);
rep(i, n) cnt[s[i]]++;
rep(i, m-1) cnt[i+1] += cnt[i];
rep(i, n) sa[--cnt[s[i]]][0] = i;
ord[sa[0][0]][0] = 0;
rep2(i, 1, n-1){
int a = sa[i-1][0], b = sa[i][0];
ord[b][0] = ord[a][0] + (s[a] < s[b]);
}
fill(all(cnt), 0);
vector<int> tmp(n);
rep(k, log_n){
rep(i, n) tmp[i] = sa[i][k]+(n-(1<<k)), tmp[i] %= n;
rep(i, n) cnt[ord[tmp[i]][k]]++;
rep(i, m-1) cnt[i+1] += cnt[i];
rep3(i, n-1, 0) sa[--cnt[ord[tmp[i]][k]]][k+1] = tmp[i];
ord[sa[0][k+1]][k+1] = 0;
rep2(i, 1, n-1){
int a = sa[i-1][k+1], b = sa[i][k+1];
pii p = {ord[a][k], ord[(a+(1<<k))%n][k]};
pii q = {ord[b][k], ord[(b+(1<<k))%n][k]};
ord[b][k+1] = ord[a][k+1] + (p < q);
}
fill(all(cnt), 0);
}
}
int operator [] (int i) const {return sa[i][log_n];}
//l文字分のsuffix-array
void subsuffix_array(int l, vector<int> &SA, vector<int> &ORD){
SA.resize(n), ORD.resize(n);
vector<int> cnt(m, 0);
int sum = 0;
vector<int> tmp(n), memo(n);
rep(k, log_n+1){
if(!(l&(1<<k))) continue;
if(sum == 0){
rep(i, n) SA[i] = sa[i][k], ORD[i] = ord[i][k];
}
else{
rep(i, n) tmp[i] = sa[i][k]+(n-sum), tmp[i] %= n;
rep(i, n) cnt[ORD[tmp[i]]]++;
rep(i, m-1) cnt[i+1] += cnt[i];
rep3(i, n-1, 0) SA[--cnt[ORD[tmp[i]]]] = tmp[i];
memo[SA[0]] = 0;
rep2(i, 1, n-1){
int a = SA[i-1], b = SA[i];
pii p = {ORD[a], ord[(a+sum)%n][k]};
pii q = {ORD[b], ord[(b+sum)%n][k]};
memo[b] = memo[a] + (p < q);
}
swap(ORD, memo);
fill(all(cnt), 0);
}
sum += 1<<k;
}
}
int size() const {return n;}
};
struct Longest_Common_Prefix_Array{
const Suffix_Array sa;
const int n;
vector<int> lcp, ord;
Longest_Common_Prefix_Array(const Suffix_Array &sa) : sa(sa), n(sa.size()-1){
lcp.assign(n, 0), ord.assign(n+1, 0);
lcp[0] = 0;
rep(i, n+1) ord[sa[i]] = i;
int h = 0;
rep(i, n){
int j = sa[ord[i]-1];
if(h > 0) h--;
while(max(i, j)+h < n && sa.s[i+h] == sa.s[j+h]) h++;
lcp[ord[i]-1] = h;
}
}
int operator [] (int i) const {return lcp[i];}
};
template<typename Monoid>
struct Segment_Tree{
Monoid ope(Monoid a, Monoid b){
return min(a, b);
}
const Monoid unit;
int n;
vector<Monoid> seg;
Segment_Tree(int N, const Monoid &x) : unit(x){
n = 1;
while(n < N) n <<= 1;
seg.assign(2*n, unit);
}
void change(int i, const Monoid &x){
i += n;
seg[i] = x;
while(i > 0){
i /= 2;
seg[i] = ope(seg[2*i], seg[2*i+1]);
}
}
Monoid query(int a, int b, int i = 1, int l = 0, int r = -1){
if(r < 0) r = n;
if(a >= r || b <= l) return unit;
if(a <= l && r <= b) return seg[i];
Monoid vl = query(a, b, 2*i, l, (l+r)/2);
Monoid vr = query(a, b, 2*i+1, (l+r)/2, r);
return ope(vl, vr);
}
Monoid operator [] (int i) const {return seg[n+i];}
void clear(){
fill(seg.begin(), seg.end(), unit);
}
};
int main(){
ll N;
cin >> N;
string s[N];
rep(i, N) cin >> s[i];
int n = 0, pos[N];
rep(i, N) pos[i] = n, n += sz(s[i]);
string S(n, 'a');
rep(i, N){
rep(j, sz(s[i])) S[pos[i]+j] = s[i][j];
}
Suffix_Array sa(S);
vector<int> ord(n+1);
rep(i, n+1) ord[sa[i]] = i;
Longest_Common_Prefix_Array lcp(sa);
Segment_Tree<int> seg(n, inf);
rep(i, n) seg.change(i, lcp[i]);
int M; ll x, d;
cin >> M >> x >> d;
ll ans = 0;
rep(i, M){
int a = x/(N-1), b = x%(N-1);
if(a > b) swap(a, b);
else b++;
int tmp = min(sz(s[a]), sz(s[b]));
a = ord[pos[a]], b = ord[pos[b]];
if(a > b) swap(a, b);
//chmin(tmp, seg.query(a, b));
ans += tmp;
x += d, x %= N*(N-1);
}
cout << ans << endl;
}