Submission #344500

#	Time	Username	Problem	Language	Result	Execution time	Memory
344500		12tqian	Palindromes (APIO14_palindrome)	C++17	100 / 100	551 ms	63692 KiB

palindrome

#include <bits/stdc++.h>
 
template <class T> struct SparseTable {
    std::vector<T> v;
    std::vector<std::vector<int>> jump;
    int level(int x) {
        return 31 - __builtin_clz(x);
    }
    int comb(int a, int b) {
        return v[a] == v[b] ? std::min(a, b) : (v[a] < v[b] ? a : b);
    }
    void init(const std::vector<T>& _v) {
        v = _v;
        jump = {std::vector<int>((int) v.size())};
        iota(jump[0].begin(), jump[0].end(), 0);
        for (int j = 1; (1 << j) <= (int) v.size(); j++) {
            jump.push_back(std::vector<int>((int) v.size() - (1 << j) + 1));
            for (int i = 0; i < (int) jump[j].size(); i++) {
                jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
            }
        }
    }
    int index(int l, int r) {
        assert(l <= r);
        int d = level(r - l + 1);
        return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
    }
    T query(int l, int r) {
        return v[index(l, r)];
    }
};

struct SuffixArray {
    std::string s;
    int n;
    std::vector<int> sa, isa, lcp;
    SparseTable<int> S;
    void init(std::string _s) {
        n = (int) (s = _s).size() + 1;
        gen_suffix_array();
        gen_lcp_array();
        gen_finish();
    }
    void gen_suffix_array() {
        sa = isa = std::vector<int>(n);
        sa[0] = n - 1;
        iota(1 + sa.begin(), sa.end(), 0);
        sort(1 + sa.begin(), sa.end(), [&](int a, int b) {
            return s[a] < s[b];
        });
        for (int i = 1; i < n; i++) {
            int a = sa[i - 1], b = sa[i];
            isa[b] = i > 1 && s[a] == s[b] ? isa[a] : i;
        }
        for (int len = 1; len < n; len *= 2) {
            std::vector<int> ss(sa), is(isa), pos(n);
            iota(pos.begin(), pos.end(), 0);
            for (auto& t : ss) {
                int tt = t - len;
                if (tt >= 0) 
                    sa[pos[isa[tt]]++] = tt;
            }
            for (int i = 1; i < n; i++) {
                int a = sa[i - 1], b = sa[i];
                isa[b] = is[a] == is[b] && is[a + len] == is[b + len] ? isa[a] : i;
            }
        }
    }
    void gen_lcp_array() {
        lcp = std::vector<int>(n - 1);
        int h = 0;
        for (int b = 0; b < n - 1; b++) {
            int a = sa[isa[b] - 1];
            while (a + h < (int) s.size() && s[a + h] == s[b + h]) 
                h++;
            lcp[isa[b] - 1] = h;
            if (h) h--;
        }
    }
    void gen_finish() {
        lcp.erase(lcp.begin());
        sa.erase(sa.begin());
        for (int i = 0; i < (int) isa.size(); i++) 
            isa[i]--;
        n--; 
        isa.pop_back();
        S.init(lcp);
    }
    int get_lcp(int a, int b) {
        if (a == b) {
            return (int) s.size() - a;
        }
        int l = isa[a], r = isa[b]; 
        if (l > r) std::swap(l, r);
        return S.query(l, r - 1);
    }
};
 
std::vector<int> manacher(std::string s) {
    std::string t = "@";
    for (auto& c : s) 
        t += c, t += '#';
    t.back() = '&';
    std::vector<int> res((int) t.size() - 1);
    int lo = 0, hi = 0;
    for (int i = 1; i < (int) t.size() - 1; i++) {
        if (i != 1)
            res[i] = std::min(hi - i, res[hi - i + lo]);
        while (t[i - res[i] - 1] == t[i + res[i] + 1])
            res[i]++;
        if (i + res[i] > hi)
            lo = i - res[i], hi = i + res[i];
    }
    res.erase(res.begin());
    for (int i = 0; i < (int) res.size(); i++)
        if ((i & 1) == (res[i] & 1))
            res[i]++;
    return res;
}

struct IntervalJoin {
    std::vector<int> e;
    std::vector<std::pair<int, int>> interval;
    void init(int n) {
        e = std::vector<int>(n, -1);
        interval.resize(n);
        for (int i = 0; i < n; i++) {
            interval[i].first = interval[i].second = i;
        }
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    bool same_set(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) std::swap(x, y);
        interval[x].first = std::min(interval[x].first, interval[y].first);
        interval[x].second = std::max(interval[x].second, interval[y].second);
        e[x] += e[y]; e[y] = x;
        return true;
    }
    std::pair<int, int> get_interval(int x) {
        x = get(x);
        return interval[x];
    }
};
 
template <class T> struct BIT {
    std::vector<T> bit;
    int n;
    void init(int n_) {
        n = n_;
        bit.resize(n);
    }
    void init(std::vector<T>& a) {
        n = (int) a.size();
        a.assign(n, 0);
        for (int i = 0; i < (int) a.size(); i++) {
            add(i, a[i]);
        }
    }
    T sum(int r) {
        T ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
        return ret;
    }
    T query(int l, int r) {
        return sum(r) - sum(l - 1);
    }
    void add(int idx, T delta) {
        for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta;
    }
};

int main() {
    using namespace std;
    cin.tie(0)->sync_with_stdio(0);
    string s; cin >> s;
    int n = (int) s.size();
    SuffixArray S; S.init(s);
    vector<int> m = manacher(s);
    long long ans = 0;
    for (long long x : m) 
        ans = max(ans, x);
    {
        vector<int> pal(n);
        for (int i = 1; i < n; i++) {
            pal[i] = m[2 * i - 1] / 2;
        }
        IntervalJoin I; I.init(n);
        vector<vector<int>> bucket(n);
        vector<vector<int>> gap(n);
        for (int i = 0; i < n; i++) {
            bucket[pal[i]].push_back(i);
        }
        for (int i = 0; i < n - 1; i++) {
            int i1 = S.sa[i];
            int i2 = S.sa[i + 1];
            int val = S.get_lcp(i1, i2);
            gap[val].push_back(i);
        }
        BIT<long long> bit;
        bit.init(n);
        for (int i = n - 1; i >= 0; i--) {
            for (int x : bucket[i]) {
                bit.add(S.isa[x], 1); // add 1 to a potential location
            }
            for (int x : gap[i]) {
                I.unite(x, x + 1);
            }
            for (int x : bucket[i]) {
                int y = S.isa[x];
                pair<int, int> p = I.get_interval(y);
                int res = bit.query(p.first, p.second);
                ans = max(ans, 1LL * 2 * i * res);
            }
        }
    }
    {
        vector<int> pal(n);
        for (int i = 0; i < n; i++) {
            pal[i] = m[2 * i] / 2;
        }
        vector<vector<int>> bucket(n);
        vector<vector<int>> gap(n);
        for (int i = 0; i < n; i++) {
            bucket[pal[i]].push_back(i);
        }
        for (int i = 0; i < n - 1; i++) {
            int i1 = S.sa[i];
            int i2 = S.sa[i + 1];
            int val = S.get_lcp(i1, i2);
            if (val)
                gap[val - 1].push_back(i);
        }
        IntervalJoin I; I.init(n);
        BIT<long long> bit;
        bit.init(n);
        for (int i = n - 1; i >= 0; i--) {
            for (int x : bucket[i]) {
                bit.add(S.isa[x], 1); 
            }
            for (int x : gap[i]) {
                I.unite(x, x + 1);
            }
            for (int x : bucket[i]) {
                int y = S.isa[x];
                pair<int, int> p = I.get_interval(y);
                int res = bit.query(p.first, p.second);
                ans = max(ans, 1LL * (2 * i + 1) * res);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27