Submission #563384

#	Time	Username	Problem	Language	Result	Execution time	Memory
563384		piOOE	Palindromes (APIO14_palindrome)	C++17	100 / 100	253 ms	10952 KiB

palindrome

//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

//template<typename T>
//using normal_queue = priority_queue<T, vector<T>, greater<>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;


template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }


const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18
const int N = 300002;
const int mod = 998244353;
const ld eps = 1e-9;

vector<int> t;
int sz = 1;

void init(int n) {
    while (sz < n) sz <<= 1;
    t.resize(sz << 1);
}

void st(int i, int v) {
    int x = i + sz;
    while (x) {
        t[x] = min(t[x], v);
        x >>= 1;
    }
}

int GetMin(int l, int r, int x, int lx, int rx) {
    if (l >= rx || lx >= r) return infI;
    if (l <= lx && rx <= r) return t[x];
    int m = (lx + rx) >> 1;
    return min(GetMin(l, r, x << 1, lx, m), GetMin(l, r, x << 1 | 1, m, rx));
}

int GetFirst(int l, int r, int k, int x, int lx, int rx) {
    if (l >= rx || lx >= r || t[x] >= k) return -1;
    if (lx + 1 == rx) return lx;
    int m = (lx + rx) >> 1;
    int ans = GetFirst(l, r, k, x << 1, lx, m);
    if (ans != -1) return ans;
    return GetFirst(l, r, k, x << 1 | 1, m, rx);
}

int GetLast(int l, int r, int k, int x, int lx, int rx) {
    if (l >= rx || lx >= r || t[x] >= k) return -1;
    if (lx + 1 == rx) return lx;
    int m = (lx + rx) >> 1;
    int ans = GetLast(l, r, k, x << 1 | 1, m, rx);
    if (ans != -1) return ans;
    return GetLast(l, r, k, x << 1, lx, m);
}

int GetMin(int l, int r) {
    return GetMin(l, r, 1, 0, sz);
}

int GetLast(int l, int r, int k) {
    return GetLast(l, r, k, 1, 0, sz);
}

int GetFirst(int l, int r, int k) {
    return GetFirst(l, r, k, 1, 0, sz);
}

void suf_array(string s, vector<int>& a, vector<int>& lcp) {
    if (s.empty()) return;
    if (s.back() != char(0)) s += char(0);
    int n = sz(s);
    a.resize(n), lcp.resize(n);
    vector<int> head(n), c(n), a1(n), c1(n), ar(n);
    for (int i = 0; i < n; ++i)
        a[i] = i;
    sort(all(a), [&](int i, int j) {
        return s[i] < s[j];
    });
    int color = 0;
    for (int i = 1; i < n; ++i) {
        if (s[a[i]] != s[a[i - 1]]) {
            ++color;
            head[color] = i;
        }
        c[a[i]] = color;
    }

    for (int len = 1; color + 1 < n && len < n; len <<= 1) {
        for (int i = 0; i < n; ++i) {
            int j = (a[i] - len);
            if (j < 0) j += n;
            a1[head[c[j]]++] = j;
        }
        head[0] = color = c1[a1[0]] = 0;
        pair<int, int> prev = {c[a1[0]], c[(a1[0] + len) % n]};
        for (int i = 1; i < n; ++i) {
            pair<int, int> now = {c[a1[i]], c[(a1[i] + len) % n]};
            if (now != prev) {
                ++color;
                head[color] = i;
            }
            c1[a1[i]] = color;
            swap(prev, now);
        }
        swap(a, a1), swap(c, c1);
    }
    for (int i = 0; i < n; ++i)
        ar[a[i]] = i;
    int LastLcp = 0;
    for (int i = 0; i < n; ++i) {
        int j = ar[i];
        if (j == n - 1) {
            continue;
        }
        j = a[j + 1];
        int k = max(0, LastLcp - 1);
        while (s[i + k] == s[j + k])
            ++k;
        lcp[ar[i]] = LastLcp = k;
    }
}


vector<int> manacher_odd(string s) {
    int n = (int) s.size();
    vector<int> d(n, 1);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r)
            d[i] = min(r - i + 1, d[l + r - i]);
        while (i - d[i] >= 0 && i + d[i] < n && s[i - d[i]] == s[i + d[i]])
            d[i]++;
        if (i + d[i] - 1 > r)
            l = i - d[i] + 1, r = i + d[i] - 1;
    }
    return d;
}

vector<int> manacher_even(string s) {
    int n = (int) s.size();
    vector<int> d(n, 0);
    int l = -1, r = -1;
    for (int i = 0; i < n - 1; i++) {
        if (i < r)
            d[i] = min(r - i, d[l + r - i - 1]);
        while (i - d[i] >= 0 && i + d[i] + 1 < n && s[i - d[i]] == s[i + d[i] + 1])
            d[i]++;
        if (i + d[i] > r)
            l = i - d[i] + 1, r = i + d[i];
    }
    return d;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    s += char(0);
    vector<int> a, lcp;
    suf_array(s, a, lcp);
    int n = sz(a);
    vector<int> odd, even;
    odd = manacher_odd(s);
    even = manacher_even(s);
    vector<int> dp(n);
    for (int i = 0; i < n; ++i) {
        int L = i - odd[i] + 1;
        ckmx(dp[L], (odd[i] - 1) * 2 + 1);
    }
    for (int i = 0; i < n; ++i) {
        if (even[i]) {
            int L = i - even[i] + 1;
            ckmx(dp[L], even[i] * 2);
        }
    }
    for (int i = 1; i < n; ++i) {
        ckmx(dp[i], dp[i - 1] - 2);
    }
    while (sz < n) sz <<= 1;
    t.resize(sz << 1);
    for (int i = 0; i < n; ++i) t[i + sz] = lcp[i];
    for (int i = sz - 1; i > 0; --i) {
        t[i] = min(t[i << 1], t[i << 1 | 1]);
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        int x = dp[a[i]];
        int R = GetFirst(i, n, x);
        if (R == -1) R = i;
        int L = GetLast(0, i, x);
        L += 1;
        ckmx(ans, ((ll) R - L + 1) * x);
    }
    cout << ans;
    return 0;
}

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