Submission #16193

#	Time	Username	Problem	Language	Result	Execution time	Memory
16193		erdemkiraz	Palindromes (APIO14_palindrome)	C++14	73 / 100	1000 ms	65864 KiB

palindrome

#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)
#define hash ___hash

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + 333;

const int N = 3e5 + 5;
const int LOG = 19;
const int ODD = 0;
const int EVEN = 1;
const int QU = 2;

int n;
char s[N];

class event{ public:
    int x, id, type;
    bool operator<(event oth) const {
        if(x != oth.x)
            return x < oth.x;
        return type < oth.type;
    }
};

int go_odd[N], go_even[N], tmp[N << 1], rad[N << 1];

void manacher() {
    int m = n * 2 + 1;
    for(int i = 0; i < m; i++)
        tmp[i] = '#';
    for(int i = 0; i < n; i++)
        tmp[i * 2 + 1] = s[i + 1];
    int i = 0, j = 0;
    while(i < m) {
        while(i - j >= 0 and i + j < m and tmp[i - j] == tmp[i + j])
            j++;
        rad[i] = j;
        int k = 1;
        while(rad[i - k] < rad[i] - k) {
            rad[i + k] = rad[i - k];
            k++;
        }
        i += k;
        j = max(0, j - k);
    }
    for(int i = 1; i <= n; i++)
        go_odd[i] = rad[(i - 1) * 2 + 1] / 2;
    for(int i = 1; i <= n; i++)
        go_even[i - 1] = rad[(i - 1) * 2] / 2;
}

int suf[N], order[N], lcp_table[N], sum[N], size[N];
pair < ii, int > p[N], temp_p[N];

void fast_sort() {
    for(int i = 1; i <= n; i++)
        size[p[i].first.second]++;
    sum[0] = 0;
    for(int i = 1; i < N; i++) {
        sum[i] = sum[i - 1] + size[i - 1];
        size[i - 1] = 0;
    }
    for(int i = 1; i <= n; i++)
        temp_p[++sum[p[i].first.second]] = p[i];
    for(int i = 1; i <= n; i++)
        size[temp_p[i].first.first]++;
    sum[0] = 0;
    for(int i = 1; i < N; i++) {
        sum[i] = sum[i - 1] + size[i - 1];
        size[i - 1] = 0;
    }
    for(int i = 1; i <= n; i++)
        p[++sum[temp_p[i].first.first]] = temp_p[i];
}

bool one_pass(int k) {
    for(int i = 1; i <= n; i++)
        p[i] = {{suf[i], i + (1 << k) <= n ? suf[i + (1 << k)] : 0}, i};
    //fast_sort();
    sort(p + 1, p + n + 1);
    int ptr = 1;
    for(int i = 1; i <= n; i++) {
        if(i - 1 >= 1 and p[i - 1].first != p[i].first)
            ptr++;
        suf[p[i].second] = ptr;
    }
    return ptr == n;
}

void build_sa() {
    for(int i = 1; i <= n; i++)
        suf[i] = s[i];
    for(int i = 0; i < LOG; i++)
        if(one_pass(i))
            break;
    for(int i = 1; i <= n; i++)
        order[suf[i]] = i;
    //for(int i = 1; i <= n; i++)
    //    printf("order[%d] = %d\n", i, order[i]);
}

void build_lcp() {
    int j = 0;
    for(int i = 1; i <= n; i++) {
        if(suf[i] == 1)
            continue;
        while(i + j <= n and order[suf[i] - 1] + j <= n and s[i + j] == s[order[suf[i] - 1] + j])
            j++;
        lcp_table[suf[i]] = j;
        if(j)
            j--;
    }
    //for(int i = 1; i <= n; i++)
    //    printf("lcp_table[%d] = %d\n", i, lcp_table[i]);
}

int a[N];
ll ans;

void build_table() {
    vector < event > v;
    for(int i = 1; i <= n; i++) {
        v.push_back({i - go_odd[i] + 1, i, ODD});
        if(go_even[i])
            v.push_back({i - go_even[i] + 1, i, EVEN});
        v.push_back({i, i, QU});
    }
    sort(v.begin(), v.end());
    set < int > s1, s2;
    foreach(it, v) {
        int x = it -> id;
        int type = it -> type;
        //printf("len = %d x = %d type = %d\n", it -> x, x, type);
        if(type == ODD)
            s1.insert(x);
        else if(type == EVEN)
            s2.insert(x);
        else {
            int val1 = (lcp_table[suf[x]] + 2 * x - 1) / 2;
            int val2 = (lcp_table[suf[x]] + 2 * x - 2) / 2;
            set < int > :: iterator it = s1.upper_bound(val1);
            if(it != s1.begin()) {
                it--;
                a[suf[x]] = max(a[suf[x]], (*it - x) * 2 + 1);
            }
            if(s2.size()) {
                it = s2.upper_bound(val2);
                if(it != s2.begin()) {
                    it--;
                    a[suf[x]] = max(a[suf[x]], (*it - x) * 2 + 2);
                }
            }
        }
    }
    //for(int i = 1; i <= n; i++)
    //    printf("a[%d] = %d\n", i, a[i]);
}

int sz;
ii vec[N];

void solve() {
    for(int i = 1; i <= n; i++)
        ans = max(ans, (ll) max(go_odd[i] * 2 - 1, go_even[i] * 2));
    build_table();
    for(int i = 2; i <= n + 1; i++) {
        int st = i;
        while(sz and vec[sz - 1].first >= a[i]) {
            ans = max(ans, (ll) (i - vec[sz - 1].second + 1) * vec[sz - 1].first);
            st = vec[sz - 1].second;
            sz--;
        }
        vec[sz++] = ii(a[i], st);
    }
}

int main () {
    
    scanf("%s", s + 1);
    n = strlen(s + 1);
    
    manacher();
    build_sa();
    build_lcp();
    solve();
    
    printf("%lld\n", ans);
    
    return 0;
    
}

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