Submission #237091

#	Time	Username	Problem	Language	Result	Execution time	Memory
237091		nvmdava	Palindromes (APIO14_palindrome)	C++17	100 / 100	272 ms	122496 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 300005
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;


ll mx = 1;
struct Node{
    Node *c[26], *p[19];
    int sz = 0, de;
    int trav(){
        for(int i = 0; i < 26; ++i){
            if(!c[i])
                continue;
            sz += c[i] -> trav();
            delete(c[i]);
            c[i] = NULL;
        }
        mx = max(mx, 1LL * de * sz);
        return sz;
    }
    Node* go(int a){
        if(c[a])
            return c[a];
        c[a] = new Node();
        c[a] -> de = de + 2;
        c[a] -> p[0] = this;
        for(int i = 1; ; ++i){
            c[a] -> p[i] = c[a] -> p[i - 1] -> p[i - 1];
            if(!c[a] -> p[i]) break;
        }
        return c[a];
    }
} *r1 = new Node();

int d1[N];
Node *w1[N];
int a[N];

int lg[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string s;
    cin>>s;

    for(int i = 2; i < N; i <<= 1)
        lg[i] = lg[i >> 1] + 1;

    r1 -> de = -1;

    int n = s.size();
    for(int i = 0; i < n; ++i)
        a[i] = s[i] - 'a';
    
    int lo = -1, r = -1;
    for(int i = 0; i < n; ++i){
        if(r < i){
            d1[i] = 1;
            w1[i] = r1 -> go(a[i]);
        } else {
            w1[i] = w1[lo - (i - lo)];
            d1[i] = d1[lo - (i - lo)];
            int w = max(0, d1[i] - (r - i));
            d1[i] -= w;
            while(w){
                w1[i] = w1[i] -> p[lg[w & -w]];
                w -= w & -w;
            }
        }

        while(i + d1[i] < n && i - d1[i] >= 0 && a[i - d1[i]] == a[i + d1[i]]){
            w1[i] = w1[i] -> go(a[i + d1[i]]);
            ++d1[i];
        }


        ++w1[i] -> sz;
        if(r <= i + d1[i] - 1){
            r = i + d1[i] - 1;
            lo = i;
        }
    }
    r1 -> trav();

    r1 -> de = 0;
    lo = -1, r = -1;
    for(int i = 0; i < n; ++i){
        if(r < i){
            d1[i] = 0;
            w1[i] = r1;
        } else {
            w1[i] = w1[lo - (i - lo)];
            d1[i] = d1[lo - (i - lo)];
            int w = max(0, d1[i] - (r - i));
            d1[i] -= w;
            while(w){
                w1[i] = w1[i] -> p[lg[w & -w]];
                w -= w & -w;
            }
        }

        while(i + d1[i] < n && i - d1[i] - 1 >= 0 && a[i - d1[i] - 1] == a[i + d1[i]]){
            w1[i] = w1[i] -> go(a[i + d1[i]]);
            ++d1[i];
        }
        ++w1[i] -> sz;
        if(r <= i + d1[i] - 1){
            r = i + d1[i] - 1;
            lo = i;
        }
    }
    r1 -> trav();

    cout<<mx;
}

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