結果

問題 No.515 典型LCP
ユーザー tokusakuraitokusakurai
提出日時 2020-07-14 12:57:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 5,672 bytes
コンパイル時間 2,634 ms
コンパイル使用メモリ 217,496 KB
実行使用メモリ 212,640 KB
最終ジャッジ日時 2024-11-17 07:06:31
合計ジャッジ時間 35,881 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 AC 2 ms
10,496 KB
testcase_04 AC 2 ms
204,952 KB
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 -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0