Submission #866289

#	Time	Username	Problem	Language	Result	Execution time	Memory
866289		Dec0Dedd	Palindromes (APIO14_palindrome)	C++14	100 / 100	265 ms	97980 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 6e5+1;
const int K = 21;

vector<int> sort_cyclic_shifts(string const& s) {
    int n = s.size();
    const int alphabet = 256;
    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
    for (int i = 0; i < n; i++)
        cnt[s[i]]++;
    for (int i = 1; i < alphabet; i++)
        cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++)
        p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]])
            classes++;
        c[p[i]] = classes - 1;
    }

    vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0)
                pn[i] += n;
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++)
            cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; i++)
            cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--)
            p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            if (cur != prev)
                ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}


vector<int> suffix_array_construction(string s) {
    s += "$";
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin());
    return sorted_shifts;
}

vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = max(0, min(r - i, p[l + (r - i)]));
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

vector<int> manacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return res;
}

vector<int> lcp_construction(string const& s, vector<int> const& p) {
    int n = s.size();
    vector<int> rank(n, 0);
    for (int i = 0; i < n; i++)
        rank[p[i]] = i;

    int k = 0;
    vector<int> lcp(n-1, 0);
    for (int i = 0; i < n; i++) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = p[rank[i] + 1];
        while (i + k < n && j + k < n && s[i+k] == s[j+k])
            k++;
        lcp[rank[i]] = k;
        if (k)
            k--;
    }
    return lcp;
}

ll mxr[N], xc[N], vs[N], st[K][N], lg[N];

int que(int l, int r) {
    int i=lg[r-l+1];
    return min(st[i][l], st[i][r-(1<<i)+1]);
}

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

    cin>>s;

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

    int n=s.size();
    vector<int> v=suffix_array_construction(s);

    for (int i=0; i<n; ++i) vs[i+1]=v[i]+1;

    vector<int> lcp=lcp_construction(s, v);

    for (int i=1; i<n; ++i) st[0][i]=lcp[i-1];
    for (int i=1; i<K; ++i) {
        for (int j=1; j+(1<<i)<=n; ++j) {
            st[i][j]=min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
        }
    }

    vector<int> x=manacher(s);
    int sz=x.size();

    for (int i=0; i<sz; ++i) {
        if (i%2 == 1) {
            ll idx=(i+1)/2, l=idx-(x[i]+1)/2+1, r=idx+(x[i]+1)/2-1;
            xc[l]=max(xc[l], r-l+1);
        } else {
            if (i == 0 || x[i] == 1) continue;
            ll idx=i/2, l=idx-x[i]/2+1, r=idx+x[i]/2;
            xc[l]=max(xc[l], r-l+1);
        }
    }

    int val=0, j=0;
    for (int i=1; i<=n; ++i) {
        if (xc[i] >= val-2*(i-j)) val=xc[i], j=i;
        xc[i]=val-2*(i-j);
    }

    ll ans=0;
    for (int i=1; i<=n; ++i) {
        ans=max(ans, xc[vs[i]]);
        int lf=1, rf=i-1, l=i, r=i-1;
        while (lf <= rf) {
            int m=(lf+rf)/2;
            if (que(m, i-1) >= xc[vs[i]]) rf=m-1, l=m;
            else lf=m+1;
        } 
        
        lf=i, rf=n-1;
        while (lf <= rf) {
            int m=(lf+rf)/2;
            if (que(i, m) >= xc[vs[i]]) lf=m+1, r=m;
            else rf=m-1;
        } ++r;

        ans=max(ans, 1ll*(r-l+1)*xc[vs[i]]);
    } cout<<ans<<"\n";
}

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