Submission #1151648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151648		OI_Account	Palindromes (APIO14_palindrome)	C++20	73 / 100	318 ms	154908 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 600'000;
const int M = 26;
const int T = 2;
const ll MOD[T] = {1'000'000'007, 1'000'000'009};
const ll B[T] = {47, 47};

int n, a[N + 10];
int counter, last, len[N + 10], cnt[N + 10];
int lnk[N + 10], nxt[N + 10][M + 3];
pair<int, int> h[2][N + 10];
int pw[T][N + 10];

int pre[N + 10], mark[N + 10];
int fen[3][N + 10];
vector<int> st1[N + 10], en1[N + 10];
vector<int> st2[N + 10], en2[N + 10];

void readInput() {
    string str;
    cin >> str;
    n = (int) str.size();
    for (int i = 1; i <= n; i++)
        a[i] = str[i - 1] - 'a';
}

void calcHash() {
    for (int x = 0; x < 2; x++) {
        h[x][0] = {0, 0};
        for (int i = 1; i <= n; i++) {
            int idx = (x == 0? a[i]: a[n - i + 1]);
            h[x][i].first = ((ll) h[x][i - 1].first * B[0] + idx) % MOD[0];
            h[x][i].second = ((ll) h[x][i - 1].second * B[1] + idx) % MOD[1];
        }
    }
}

void calcPw() {
    for (int t = 0; t < T; t++) {
        pw[t][0] = 1;
        for (int i = 1; i <= n; i++)
            pw[t][i] = (ll) pw[t][i - 1] * B[t] % MOD[t];
    }
}

pair<ll, ll> getHash(int t, int l, int r) {
    ll res1 = ((ll) h[t][r].first - (ll) h[t][l - 1].first * (ll) pw[0][r - l + 1] % MOD[0] + MOD[0]) % MOD[0];
    ll res2 = ((ll) h[t][r].second - (ll) h[t][l - 1].second * (ll) pw[1][r - l + 1] % MOD[1] + MOD[1]) % MOD[1];
    return {res1, res2};
}

bool isPalindrome(int l, int r) {
    pair<ll, ll> p1 = getHash(0, l, r);
    pair<ll, ll> p2 = getHash(1, n - r + 1, n - l + 1);
    //cout << l << ' ' << r << ":::::: " << (p1 == p2) << endl;
    return p1 == p2;
}

int newVer(int v = 0) {
    int u = ++counter;
    if (v)
        for (int j = 0; j < M; j++)
            nxt[u][j] = nxt[v][j];
    return u;
}

int calcFirstHave(int pnt, int newLast, int c) {
    while (pnt && !nxt[pnt][c]) {
        nxt[pnt][c] = newLast;
        pnt = lnk[pnt];
    }
    return pnt;
}

void changeTillHave(int pnt, int c, int x, int y) {
    while (pnt && nxt[pnt][c] == x) {
        nxt[pnt][c] = y;
        pnt = lnk[pnt];
    }
}

void addChar(int c) {
    int idx = calcFirstHave(last, newVer(), c);
    len[counter] = len[last] + 1;
    last = counter;
    if (!idx || len[nxt[idx][c]] == len[idx] + 1) 
        lnk[last] = (idx? nxt[idx][c]: 1);
    else {
        int v = nxt[idx][c], u = newVer(nxt[idx][c]);
        changeTillHave(idx, c, v, u);
        lnk[u] = lnk[v];
        len[u] = len[idx] + 1;
        lnk[v] = lnk[last] = u;
    }
}

void calcSuffixAuto() {
    counter = 1;
    last = 1;
    for (int i = 1; i <= n; i++)
        addChar(a[i]);
}

void calcCnt() {
    for (int pnt = last; pnt != 1; pnt = lnk[pnt])
        cnt[pnt] = 1;
    vector<pair<int, int>> vec;
    for (int i = 1; i <= counter; i++)
        vec.push_back({len[i], i});
    sort(vec.begin(), vec.end());
    for (int i = counter - 1; i >= 0; i--) {
        int u = vec[i].second;
        for (int j = 0; j < M; j++)
            cnt[u] += cnt[nxt[u][j]];
    }
}

void calcPre() {
    pre[0] = 1;
    for (int i = 1; i <= n; i++)
        pre[i] = nxt[pre[i - 1]][a[i]];
    for (int i = 1; i <= n; i++)
        if (!mark[pre[i]])
            for (int j = pre[i]; j != 1 && !mark[j]; j = lnk[j])
                mark[j] = i;
}

void update(int t, int idx, int val) {
    for (; idx <= n; idx += idx & -idx)
        fen[t][idx] += val;
}

int get(int t, int idx) {
    int res = 0;
    for (; idx; idx -= idx & -idx)
        res += fen[t][idx];
    return res;
}

int getFirst(int t, int low) {
    int idx = 0, remain = get(t, low - 1);
    for (int j = M; j >= 0; j--)
        if (idx + (1 << j) <= n && fen[t][idx + (1 << j)] <= remain) {
            idx += (1 << j);
            remain -= fen[t][idx];
        }
    return idx + 1;
}

pair<int, int> calcSeg1(int i) {
    int l = 0, r = min(i, n - i + 1);
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (isPalindrome(i - mid, i + mid))
            l = mid;
        else
            r = mid;
    }
    return {i, i + l};
}

pair<int, int> calcSeg2(int i) {
    int l = 1, r = min(i, n - i + 2);
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (isPalindrome(i - mid, i + mid - 1))
            l = mid;
        else
            r = mid;
    }
    return {i, i + l - 1};
}

void calcStEn() {
    for (int i = 1; i <= n; i++) {
        //cout << "p1 " << endl;
        pair<int, int> p1 = calcSeg1(i);
        st1[p1.first].push_back(i);
        en1[p1.second].push_back(i);
        //cout << "p2" << endl;
        if (1 < i && a[i] == a[i - 1]) {
            pair<int, int> p2 = calcSeg2(i);
            st2[p2.first].push_back(i);
            en2[p2.second].push_back(i);
        }
        //cout << i << ": " << p1.first << ' ' << p1.second << endl;
    }
    for (int i = 1; i <= n; i++) {
        st1[i].shrink_to_fit();
        en1[i].shrink_to_fit();
        st2[i].shrink_to_fit();
        en2[i].shrink_to_fit();
    }
}

ll check1(int l, int r, int u) {
    int mid1 = (r + l + 1) / 2;
    mid1 = getFirst(1, mid1);
    if (mid1 <= r)
        return (ll) (2 * (r - mid1) + 1) * (ll) cnt[u];
    return 0;
}

ll check2(int l, int r, int u) {
    if (l == r)
        return 0;
    int mid2 = (r + l + 2) / 2;
    mid2 = getFirst(2, mid2);
    if (mid2 <= r)
        return (ll) (2 * (r - mid2 + 1)) * (ll) cnt[u];
    return 0;
}

ll calcAns(int i) {
    if (mark[pre[i]] != i)
        return 0;
    ll res = 0;
    for (int u = pre[i]; u != 1 && mark[u] == i; u = lnk[u]) {
        int r = i;
        int l = i - len[u] + 1;
        res = max(res, check1(l, r, u));
        res = max(res, check2(l, r, u));
    }
    return res;
}

void calcAns() {
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (auto idx: st1[i])
            update(1, idx, 1);
        for (auto idx: st2[i])
            update(2, idx, 1);
        ans = max(ans, calcAns(i));
        for (auto idx: en1[i])
            update(1, idx, -1);
        for (auto idx: en2[i])
            update(2, idx, -1);
    }
    cout << ans << flush;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcHash();
    calcPw();
    calcSuffixAuto();
    calcCnt();
    calcPre();
    calcStEn();
    calcAns();
    return 0;
}

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