Submission #249159

#	Time	Username	Problem	Language	Result	Execution time	Memory
249159		receed	Palindromes (APIO14_palindrome)	C++14	0 / 100	1093 ms	2816 KiB

palindrome

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 600001, M = 1 << 19;
string s;
int mp[N], mx[N], ord[N], c[N], cnt[N], a[N], n, pc[N], pord[N], lcp[N], pos[N], tr[M * 2];

int getl(int p, int m, int v=1, int l=0, int r=N) {
    if (tr[v] >= m || p <= l)
        return -1;
    if (r - l == 1)
        return l;
    int x = getl(p, m, v * 2 + 1, (l + r) / 2, r);
    if (x != -1)
        return x;
    return getl(p, m, v * 2, l, (l + r) / 2);
}

int getr(int p, int m, int v=1, int l=0, int r=N) {
    if (tr[v] >= m || r <= p)
        return n;
    if (r - l == 1)
        return l;
    int x = getr(p, m, v * 2, l, (l + r) / 2);
    if (x != n)
        return x;
    return getr(p, m, v * 2 + 1, (l + r) / 2, r);
}

int sm(int x, int y) {
    return x + y >= n ? x + y - n : x + y;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> s;
    n = s.size();
    int l = 0, r = 0;
    rep(i, 2 * n - 1) {
        if (i <= 2 * r)
            mp[i] = min(mp[(l + r) * 2 - i], r * 2 - i + 1);
        if (i % 2 == 0)
            mp[i] = max(mp[i], 1);
        while (i - mp[i] - 1 >= 0 && (i + mp[i] + 1) / 2 < n && s[(i - mp[i] - 1) / 2] == s[(i + mp[i] + 1) / 2])
            mp[i] += 2;
        if ((i + mp[i] - 1) / 2 > r) {
            l = (i + mp[i] + 1) / 2;
            r = (i + mp[i] - 1) / 2;
        }
    }
    int ps = 2 * n - 1;
    for (int i = n - 1; i >= 0; i--) {
        while (mp[ps] < ps - i * 2 + 1)
            ps--;        
        mx[i] = ps - i * 2 + 1;
    }
    // rep(i, 2 * n - 1)
    //     cout << mp[i] << '\n';
    // rep(i, n)
    //     cout << mx[i] << '\n';
    n++;
    rep(i, n) {
        a[i] = (i == n - 1 ? 0 : s[i] - 'a' + 1);
        cnt[a[i] + 1]++;
    }
    rep(i, 27)
        cnt[i + 1] += cnt[i];
    rep(i, n)
        ord[cnt[a[i]]++] = i;
    int cc = 1;
    rep(i, n - 1) {
        c[ord[i + 1]] = c[ord[i]];
        if (s[ord[i]] != s[ord[i + 1]]) {
            c[ord[i + 1]]++;
            cc++;
        }
    }
    for (int l = 1; l < n; l++) {
        rep(i, cc + 1)
            cnt[i] = 0;
        rep(i, n) {
            cnt[c[i] + 1]++;
            pord[i] = ord[i];
            pc[i] = c[i];
        }
        rep(i, cc)
            cnt[i + 1] += cnt[i];
        rep(i, n) {
            int q = pord[i] - l;
            if (q < 0)
                q += n;
            ord[cnt[c[q]]++] = q;
        }
        c[ord[0]] = 0;
        rep(i, n - 1) {
            c[ord[i + 1]] = c[ord[i]];
            if (pc[ord[i]] != pc[ord[i + 1]] || pc[sm(ord[i], l)] != pc[sm(ord[i + 1], l)])
                c[ord[i + 1]]++;
        }
        cc = c[ord[n - 1]] + 1;
    }
    rep(i, n)
        pos[ord[i]] = i;
    cc = 0;
    for (int i = n - 1; i >= 0; i--) {
        cc = max(cc - 1, 0);
        if (pos[i] == n - 1)
            cc = 0;
        else
            while (s[i + cc] == s[ord[pos[i] + 1] + cc])
                cc++;
        lcp[pos[i]] = cc;
    }
    rep(i, n) {
        // cout << ord[i] << '\n';
        // cout << s.substr(ord[i]) << '\n';
    }
    rep(i, n - 1)
        tr[N + i] = lcp[i];
    for (int i = N - 1; i > 0; i--)
        tr[i] = min(tr[i * 2], tr[i * 2 + 1]);
    ll ans = 0;
    rep(i, n) {
        ll cl = getl(pos[i], mp[i]), cr = getr(pos[i], mp[i]);
        ans = max(ans, (cr - cl) * mp[i]);
    }
    cout << ans;
}

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