Submission #848969

#	Time	Username	Problem	Language	Result	Execution time	Memory
848969		treap_enjoyer	Palindromes (APIO14_palindrome)	C++14	0 / 100	274 ms	61808 KiB

palindrome

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;


const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;

int n;
string s;
vector<ll> h;
vector<ll> p;
vector<int> d1;
vector<int> d2;
vector<int> arr;
void calc(){
    h.resize(n + 1);
    p.resize(n + 1, 1);
    for(int i = 1; i < n; i++){
        p[i] *= p[i - 1];
        p[i] %= INF;
    }
    for(int i = 0; i < n; i++){
        if(i) h[i] += h[i - 1];
        h[i] += (s[i] - 'a' + 1) * p[i];
        h[i] %= INF;
    }
}
void man(){
    d1.resize(n, 0);
    d2.resize(n, 0);
    int l = 0, r = -1;
    for(int i = 0; i < n; i++){
        int k = i > r ? 1 : min(d1[l + r - i], r - i + 1);
        while(i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
        d1[i] = k;
        if(i + k - 1 > r){
            r = i + k - 1;
            l = i - k + 1;
        }
    }
    l = 0, r = -1;
    for(int i = 0; i < n; i++){
        int k = i > r ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while(i - k - 1 >= 0 && i + k < n && s[i + k] == s[i - k - 1]) k++;
        d2[i] = k;
        if(i + k - 1 > r){
            l = i - k, r = i + k - 1;
        }
    }
}
void sufmas(){
    arr.resize(n + 1);
    vector<int> c(n + 1, 0);
    vector<int> c1(n + 1);
    vector<int> arr1(n + 1);
    s += '#';
    map<int, vector<int> > cnt;
    for(int i = 0; i <= n; i++){
        cnt[s[i] - 'a'].push_back(i);
    }
    int sch = 0; 
    int sch1 = 0;
    for(auto i: cnt){
        for(auto j: i.second){
            arr[sch] = j;
            c[j] = sch1;
            sch++;
        }
        if(i.second.size()) sch1++;
    }
    cnt.clear();
    vector<vector<int> > q(n + 1);
    for(int k = 0; k < 19; k++){
        for(int i = 0; i <= n; i++){
            //cout << (arr[i] + (1 << k)) % (n + 1) << " " << c[(arr[i] + (1 << k)) % (n + 1)] << endl;
            q[c[(arr[i] + (1 << k)) % (n + 1)]].push_back(arr[i]);
        }
        sch = 0;
        for(int i = 0; i <= n; i++){
            for(auto j: q[i]){
                arr1[sch] = j;
                sch++;
            }
            q[i].clear();
        }
        arr.swap(arr1);
        for(int i = 0; i <= n; i++){
            q[c[arr[i]]].push_back(arr[i]);
        }
        sch = 0;
        for(int i = 0; i <= n; i++){
            for(auto j: q[i]){
                arr1[sch] = j;
                sch++;
            }
            q[i].clear();
        }
        arr.swap(arr1);
        c1[arr[0]] = 0;
        sch = 0;
        int a1, a2, b1, b2;
        for(int i = 1; i <= n; i++){
            a1 = c[arr[i]];
            a2 = c[arr[i - 1]];
            b1 = c[(arr[i] + (1 << k)) % (n + 1)];
            b2 = c[(arr[i - 1] + (1 << k)) % (n + 1)];
            if(a1 != a2 || b1 != b2) sch++;
            c1[arr[i]] = sch;
        }
        c.swap(c1);
    }
}
bool cmp(int a, int b, int cnt){
    if(a + cnt > n || b + cnt > n) return 0;
    ll h1 = h[a + cnt - 1];
    ll h2 = h[b + cnt - 1];
    if(a) h1 = (h1 - h[a - 1] + INF) % INF;
    if(b) h2 = (h2 - h[b - 1] + INF) % INF;
    if(b > a) h1 = (h1 * 1LL * p[b - a]) % INF;
    if(a > b) h2 = (h2 * 1LL * p[a - b]) % INF;
    return h1 == h2;
}
int bin_search(int pos, int cnt){
    if(cnt == 0) return 0;
    int l = 1, r = pos;
    int l1 = 0, r1 = 0;
    while(l <= r){
        int mid = (l + r) / 2;
        if(cmp(arr[mid], arr[pos], cnt)){
            l1 = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    l = pos, r = n;
    while(l <= r){
        int mid = (l + r) / 2;
        if(cmp(arr[mid], arr[pos], cnt)){
            r1 = mid;
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    return r1 - l1 + 1;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    cin >> s;
    n = s.size();
    calc();
    man();
    sufmas();
    vector<int> c(n + 1, 0);
    for(int i = 1; i <= n; i++){
        c[arr[i]] = i;
    }
    /*for(int i = 1; i <= n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;*/
    ll ans = 0;
    for(int i = 0; i < n; i++){
       // cout << i << " " << d1[i] << " " << d2[i] << " " << c[i - d1[i] + 1] << " " << c[i - d2[i]] << " ----> " << bin_search(c[i - d1[i] + 1], d1[i] * 2 - 1) << " " << bin_search(c[i - d2[i]], d2[i] * 2) << endl;
        ans = max(ans, (d1[i] * 2 - 1) * 1LL * bin_search(c[i - d1[i] + 1], d1[i] * 2 - 1));
        ans = max(ans, (d2[i] * 2) * 1LL * bin_search(c[i - d2[i]], d2[i] * 2));
    }
    cout << ans << endl;
}

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