Submission #1185058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185058		boxfish	Palindromes (APIO14_palindrome)	C++20	100 / 100	89 ms	87484 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 5;
const ll base = 31;
const ll mod = 1e9 + 7;
string S;
int D_odd[N], D_even[N], n;
ll hashT[N], P10[N];

struct node{
    int l, r;
    ll s;
};

map<int,node> mp[N];
map<int,bool> F[N];

ll Ans = 0;

ll get(int i,int j) {
    ll s = hashT[i - 1]  * P10[j - i + 1] % mod;
    //cout << s << ' ' << hashT[j] - s  << '\n';
    s = hashT[j] - s;
    //cout << s << "!\n";
    //cout << s << "!\n";
    if(s < 0) s += mod;
    //cout << s << "!\n";
    //return (hashT[j] - (hashT[i - 1] * P10[j - i + 1] % mod) + mod) % mod;
    return s;
}


void Cal_D_odd(){
    int L = 1;
    int R = 0;
    for(int i = 1 ; i <= n ; ++i){
        if(i > R) D_odd[i] = 0;
        else D_odd[i] = min(R - i,D_odd[R - i + L]);
        while(i - D_odd[i] - 1 > 0 && i + D_odd[i] + 1 <= n && S[i - D_odd[i] - 1] == S[i + D_odd[i] + 1]){
            D_odd[i]++;
        }
        if(i + D_odd[i] > R){
            R = i + D_odd[i];
            L = i - D_odd[i];
        }
        int sz = D_odd[i] * 2 + 1;
        //cout << i << "." << sz << "====\n";
        if(sz > 0){
            ll s = get(i - D_odd[i], i + D_odd[i]);
           // cout << i - D_odd[i] << ' ' << i + D_odd[i] << ' ' << s << '\n';
            int _l = i - D_odd[i];
            int _r = i + D_odd[i];

            if(_l <= _r && !F[sz][s]){
                mp[sz][s] = {_l,_r,1};
                F[sz][s] = 1;
            }
            else
                mp[sz][s].s += 1;
        }
    }
}

void Cal_D_even(){
    int L = 1;
    int R = 0;
    for(int i = 1 ; i < n ; ++i){
        int j = i + 1;
        if(j > R) D_even[i] = 0;
        else D_even[i] = min(R - j + 1,D_even[R + L - j]);
        while(i - D_even[i] > 0 && j + D_even[i] <= N && S[i - D_even[i]] == S[j + D_even[i]])
            D_even[i]++;
        if(i + D_even[i] > R){
            R = i + D_even[i];
            L = j - D_even[i];
        }
        int sz = D_even[i] * 2;
        if(sz > 0){
            ll s = get(j - D_even[i], i + D_even[i]);
            //cout << D_even[i] << ' ' << j - D_even[i] << ' ' << i + D_even[i] << ' ' << s << '\n';
            int _l = j - D_even[i];
            int _r = i + D_even[i];

            if(_l <= _r && !F[sz][s]){
                mp[sz][s] = {_l,_r,1};
                F[sz][s] = 1;
            }
            else
                mp[sz][s].s += 1;
        }

    }
}


int main(){
    cin >> S;
    n = S.length();
    S = ' ' + S;
    P10[0] = 1;
    for(int i = 1 ; i <= n + 5; ++i) P10[i] = P10[i - 1] * base % mod;
    for(int i = 1 ; i <= n ; ++i) hashT[i] = hashT[i - 1] * base % mod + (S[i] - 'a' + 1) % mod;
    //cout << get(12,14) << "!\n";
    Cal_D_even();
    Cal_D_odd();

    for(ll i = n ; i >= 1 ; --i){
        //cout << i << "====\n";
        for(pair<int,node> j : mp[i]){
            Ans = max(Ans, i * j.second.s);
            //cout << j.second.l << ' ' << j.second.r << ' ' << j.second.s << '\n';
        }
        if(i - 2 >= 1)
        for(pair<int,node> j : mp[i])
        {
            ll s = get(j.second.l + 1,j.second.r - 1);

            if(!F[i - 2][s]){
                mp[i - 2][s].s += j.second.s;
                mp[i - 2][s].l = j.second.l + 1;
                mp[i - 2][s].r = j.second.r - 1;
                F[i - 2][s] = 1;
            }
            else{
                mp[i - 2][s].s += j.second.s;
            }
        }
    }
    cout << Ans ;

    return 0;
}

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