#863128 (C++17) No.515 典型LCP

提出ソース

結果

問題	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

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード