Submission #403830

#	Time	Username	Problem	Language	Result	Execution time	Memory
403830		opukittpceno_hhr	Palindromes (APIO14_palindrome)	C++17	0 / 100	1088 ms	83076 KiB

palindrome

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

typedef long long ll;

const int N = 3e5 + 7;
const int ALP = 26;

namespace Hash {
    const int MOD = 1e9 + 7;
    const int BASE = 31;

    int add(int a, int b) {
        if (a + b < MOD) {
            return a + b;
        }
        return a + b - MOD;
    }

    int sub(int a, int b) {
        if (a >= b) {
            return a - b;
        }
        return a - b + MOD;
    }

    int mul(int a, int b) {
        return 1LL * a * b % MOD;
    }

    int n;

    int pw[N];
    int h[N];
    int rh[N];

    int req(int i, int j, int len) {
        i = n - 1 - i;
        int F = sub(rh[i + len], mul(rh[i], pw[len]));
        int S = sub(h[j + len], mul(h[j], pw[len]));
        return F == S;
    }

    void init(string s) {
        n = (int)s.size();
        pw[0] = 1;
        for (int i = 0; i < n; i++) {
            pw[i + 1] = mul(pw[i], BASE);
        }
        for (int i = 0; i < n; i++) {
            h[i + 1] = add(s[i], mul(h[i], BASE));
        }
        reverse(s.begin(), s.end());
        for (int i = 0; i < n; i++) {
            rh[i + 1] = add(s[i], mul(rh[i], BASE));
        }
        reverse(s.begin(), s.end());
    }
}

namespace SparceTable {
    const int L = 20;

    int pw[N];
    int mn[L][N];

    void init(int n, int *a) {
        for (int i = 0; i < n; i++) {
            mn[0][i] = a[i];
        }
        for (int i = 0; i + 1 < L; i++) {
            for (int j = 0; j + 2 * (1 << i) <= n; j++) {
                mn[i + 1][j] = min(mn[i][j], mn[i][j + (1 << i)]);
            }
        }
        pw[1] = 0;
        for (int i = 2; i <= n; i++) {
            pw[i] = pw[i / 2] + 1;
        }
    }

    int get(int l, int r) {
        int p = pw[r - l];
        return min(mn[p][l], mn[p][r - (1 << p)]);
    }
}

namespace SuffixArray {
    int n;

    string s;

    int sa[N];
    int wr[N];

    int cur_class[N];
    tuple<int, int, int> tos[N];
    tuple<int, int, int> ntos[N];
    vector<int> by_sec[N];
    int pcnt[N];

    void do_sort() {
        // cerr << "sort " << endl;
        // for (int i = 0; i < n; i++) {
        //     cerr << get<0>(tos[i]) << ' ' << get<1>(tos[i]) << endl;
        // }
        for (int i = 0; i < n; i++) {
            pcnt[i] = 0;
            by_sec[i].clear();
        }
        for (int i = 0; i < n; i++) {
            pcnt[get<0>(tos[i])]++;
            by_sec[get<1>(tos[i])].push_back(i);
        }
        for (int i = 1; i < n; i++) {
            pcnt[i] += pcnt[i - 1];
        }
        for (int i = 0; i < n; i++) {
            pcnt[i]--;
        }
        for (int p = 0; p < n; p++) {
            for (auto i : by_sec[p]) {
                ntos[pcnt[get<0>(tos[i])]] = tos[i];
                pcnt[get<0>(tos[i])]--;
            }
        }
        for (int i = 0; i < n; i++) {
            tos[i] = ntos[i];
        }
        // cerr << "aft " << endl;
        // for (int i = 0; i < n; i++) {
        //     cerr << get<0>(tos[i]) << ' ' << get<1>(tos[i]) << endl;
        // }
    }

    void build_sa() {
        s.push_back(0);
        n++;
        {
            vector<char> hv;
            for (auto c : s) {
                hv.push_back(c);
            }
            sort(hv.begin(), hv.end());
            hv.resize(unique(hv.begin(), hv.end()) - hv.begin());
            for (int i = 0; i < n; i++) {
                cur_class[i] = lower_bound(hv.begin(), hv.end(), s[i]) - hv.begin();
            }
        }
        for (int l = 1; l < n; l *= 2) {
            for (int i = 0; i < n; i++) {
                tos[i] = make_tuple(cur_class[i], cur_class[(i + l) % n], i);
            }
            do_sort();
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                cur_class[get<2>(tos[i])] = cnt;
                if (i + 1 < n) {
                    cnt += (get<0>(tos[i]) != get<0>(tos[i + 1]) || get<1>(tos[i]) != get<1>(tos[i + 1]));
                }
            }
        }
        n--;
        for (int i = 0; i < n; i++) {
            wr[i] = cur_class[i] - 1;
        }
        for (int i = 0; i < n; i++) {
            sa[wr[i]] = i;
        }
    }

    int l[N];

    void build_lcp() {
        for (int i = 0; i < n; i++) {
            int k = 0;
            if (i > 0) {
                k = l[wr[i - 1]];
            }
            k--;
            k = max(k, 0);
            int in_l = wr[i];
            if (in_l + 1 == n) {
                l[in_l] = -1;
            } else {
                int j = sa[in_l + 1];
                while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
                    k++;
                }
                l[in_l] = k;
            }
        }
        SparceTable::init(n, l);
    }

    int lcp(int i, int j) {
        if (i == j) {
            return n - i;
        }
        i = wr[i];
        j = wr[j];
        if (i > j) swap(i, j);
        return SparceTable::get(i, j);
    }

    void init(string s_) {
        s = s_;
        n = (int)s.size();
        build_sa();
        build_lcp();
    }
}

void solve(vector<int> v, int ml, int add, ll &ans) {
    int n = (int)v.size();
    vector<int> l(n);
    vector<int> r(n);
    {
        vector<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && v[st.back()] >= v[i]) {
                st.pop_back();
            }
            if (st.empty()) {
                l[i] = -1;
            } else {
                l[i] = st.back();
            }
            st.push_back(i);
        }
    }
    {
        vector<int> st;
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && v[st.back()] >= v[i]) {
                st.pop_back();
            }
            if (st.empty()) {
                r[i] = n;
            } else {
                r[i] = st.back();
            }
            st.push_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        ans = max(ans, (ll)(r[i] - l[i]) * (v[i] * ml + add));
    }
}

int cnt[ALP];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;
    int n = (int)s.size();

    Hash::init(s);
    SuffixArray::init(s);
    ll ans = 0;

    auto cmp = [&](pair<int, int> X, pair<int, int> Y) {
        int i1, len1, i2, len2;
        tie(i1, len1) = X;
        tie(i2, len2) = Y;
        int sk = SuffixArray::lcp(i1, i2);
        if (sk >= len1 || sk >= len2) {
            return len1 < len2;
        }
        i1 += sk;
        i2 += sk;
        return (i1 == n || s[i1] < s[i2]);
    };

    //single
    {
        for (int i = 0; i < n; i++) {
            cnt[s[i] - 'a']++;
            ans = max(ans, (ll)cnt[s[i] - 'a']);
        }
    }

    //even
    {
        vector<pair<int, int>> ip;
        for (int i = 0; i < n; i++) {
            int mx = -1;
            int l = -1;
            int r = n +1;
            while (r  - l > 1) {
                int mid = (r + l) / 2;
                if (mid <= i && mid + i <= n && Hash::req(i - 1, i, mid)) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            mx = l;
            ans = max(ans, (ll)2 * mx);
            if (mx != -1) {
                ip.push_back({i, mx});
            }
        }
        sort(ip.begin(), ip.end(), cmp);
        vector<int> val;
        for (int i = 0; i + 1 < (int)ip.size(); i++) {
            val.push_back(min({ip[i].second, ip[i + 1].second, SuffixArray::lcp(ip[i].first, ip[i + 1].first)}));
        }
        solve(val, 2, 0, ans);
    }
    //odd
    {
        vector<pair<int, int>> ip;
        for (int i = 0; i < n; i++) {
            int mx = -1;
            int l = -1;
            int r = n +1;
            while (r  - l > 1) {
                int mid = (r + l) / 2;
                if (mid <= i && mid + i + 1 <= n && Hash::req(i - 1, i + 1, mid)) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            mx = l;
            ans = max(ans, (ll)2 * mx + 1);
            if (mx != -1) {
                ip.push_back({i, mx + 1});
            }
        }
        sort(ip.begin(), ip.end(), cmp);
        vector<int> val;
        for (int i = 0; i + 1 < (int)ip.size(); i++) {
            val.push_back(min({ip[i].second,  ip[i + 1].second, SuffixArray::lcp(ip[i].first, ip[i + 1].first)}));
        }
        solve(val, 2, -1, ans);
    }
    cout << ans << endl;
}

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