結果
問題 | No.515 典型LCP |
ユーザー |
![]() |
提出日時 | 2024-09-30 01:34:15 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 538 ms / 1,000 ms |
コード長 | 2,231 bytes |
コンパイル時間 | 2,478 ms |
コンパイル使用メモリ | 136,960 KB |
実行使用メモリ | 85,820 KB |
最終ジャッジ日時 | 2024-09-30 01:34:24 |
合計ジャッジ時間 | 7,372 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;using ll = long long;#include<atcoder/string>#include<map>#line 1 "structure/others/sparse-table.hpp"/*** @brief Sparse-Table(スパーステーブル)**/template <typename T, typename F>struct SparseTable {F f;vector<vector<T> > st;vector<int> lookup;SparseTable() = default;explicit SparseTable(const vector<T> &v, const F &f) : f(f) {const int n = (int)v.size();const int b = 32 - __builtin_clz(n);st.assign(b, vector<T>(n));for (int i = 0; i < v.size(); i++) {st[0][i] = v[i];}for (int i = 1; i < b; i++) {for (int j = 0; j + (1 << i) <= n; j++) {st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);}}lookup.resize(v.size() + 1);for (int i = 2; i < lookup.size(); i++) {lookup[i] = lookup[i >> 1] + 1;}}inline T fold(int l, int r) const {int b = lookup[r - l];return f(st[b][l], st[b][r - (1 << b)]);}};template <typename T, typename F>SparseTable<T, F> get_sparse_table(const vector<T> &v, const F &f) {return SparseTable<T, F>(v, f);}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);ll n;cin>>n;vector<string> s(n);for(int i = 0;i<n;i++) cin>>s[i];string S = "";vector<int> idx(n,0);for(int i = 0;i<n;i++) {idx[i] = S.size();S += s[i];}auto sa = atcoder::suffix_array(S);auto lcp = atcoder::lcp_array(S,sa);auto f = [&](ll a,ll b) -> ll {return min(a,b);};SparseTable sp(lcp,f);int M = sa.size();vector<int> rev(M);for(int i = 0;i<M;i++) rev[sa[i]] = i;ll m,x,d;cin>>m>>x>>d;ll ans = 0;for(ll k = 1;k<=m;k++){ll i = (x/(n-1)) + 1;ll j = (x%(n-1)) + 1;if(i>j) swap(i,j);else j = j + 1;x = (x+d) % (n*(n-1));i--;j--;int ni = idx[i];int nj = idx[j];ni = rev[ni];nj = rev[nj];if(ni>nj) swap(ni,nj);ll can = min<ll>(s[i].size(),s[j].size());can = min<ll>(can,sp.fold(ni,nj));ans += can;}cout<<ans<<endl;}