Submission #1168475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168475		byunjaewoo	Palindromes (APIO14_palindrome)	C++20	0 / 100	3 ms	2632 KiB

palindrome

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=300010, P=107, Mod=1e9+9;
int n, ans, pw[N], fh[N], ih[N], c[30], g[N];
bool chk[N];
vector<pair<int, int>> vec[30];
string s;

int Find(int x) {return (g[x]>=0)?(g[x]=Find(g[x])):x;}
void Union(int u, int v) {
    u=Find(u), v=Find(v);
    if(u!=v) g[v]+=g[u], g[u]=v;
}

void f(vector<pair<int, int>> vec, int t) {
    if(vec.empty()) return;
    for(auto [l, r]:vec) ans=max(ans, (r-l+1)*2+t);
    sort(vec.begin(), vec.end(), [&](pair<int, int> x, pair<int, int> y) {
        int k=0;
        for(int s=1, e=min(x.second-x.first+1, y.second-y.first+1); s<=e; ) {
            int m=(s+e)/2;
            int tmp1=(fh[x.first+m-1]-fh[x.first-1]+Mod)%Mod; tmp1=(tmp1*pw[n-x.first+1])%Mod;
            int tmp2=(fh[y.first+m-1]-fh[y.first-1]+Mod)%Mod; tmp2=(tmp2*pw[n-y.first+1])%Mod;
            if(tmp1==tmp2) k=m, s=m+1;
            else e=m-1;
        }
        if(k==min(x.second-x.first+1, y.second-y.first+1)) return x.second-x.first<y.second-y.first;
        return s[x.first+k-1]<s[y.first+k-1];
    });
    vector<pair<int, int>> vec2;
    for(int i=0; i<vec.size()-1; i++) {
        pair<int, int> x=vec[i], y=vec[i+1];
        int k=0;
        for(int s=1, e=min(x.second-x.first+1, y.second-y.first+1); s<=e; ) {
            int m=(s+e)/2;
            int tmp1=(fh[x.first+m-1]-fh[x.first-1]+Mod)%Mod; tmp1=(tmp1*pw[n-x.first+1])%Mod;
            int tmp2=(fh[y.first+m-1]-fh[y.first-1]+Mod)%Mod; tmp2=(tmp2*pw[n-y.first+1])%Mod;
            if(tmp1==tmp2) k=m, s=m+1;
            else e=m-1;
        }
        vec2.push_back({i, k});
    }
    sort(vec2.rbegin(), vec2.rend());
    fill(g, g+n, -1), fill(chk, chk+n, false);
    for(auto [k, l]:vec2) {
        chk[k]=true;
        if(k && chk[k-1]) Union(k-1, k);
        if(chk[k+1]) Union(k, k+1);
        ans=max(ans, (-g[Find(k)]+1)*(2*l+t));
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>s, n=s.size();
    pw[0]=1;
    for(int i=1; i<N; i++) pw[i]=(pw[i-1]*P)%Mod;
    for(int i=1; i<=n; i++) fh[i]=(fh[i-1]+(s[i-1]-'a'+1)*pw[i-1])%Mod;
    for(int i=n; i>=1; i--) ih[i]=(ih[i+1]+(s[i-1]-'a'+1)*pw[n-i])%Mod;
    for(int i=1; i<n; i++) {
        int k=0;
        for(int s=1, e=min(i, n-i); s<=e; ) {
            int m=(s+e)/2;
            int tmp1=(fh[i]-fh[i-m]+Mod)%Mod; tmp1=(tmp1*pw[n-i])%Mod;
            int tmp2=(ih[i+1]-ih[i+m+1]+Mod)%Mod; tmp2=(tmp2*pw[i])%Mod;
            if(tmp1==tmp2) k=m, s=m+1;
            else e=m-1;
        }
        if(k) vec[0].emplace_back(i+1, i+k);
    }
    for(int i=1; i<=n; i++) {
        int k=0;
        for(int s=1, e=min(i-1, n-i); s<=e; ) {
            int m=(s+e)/2;
            int tmp1=(fh[i-1]-fh[i-m-1]+Mod)%Mod; tmp1=(tmp1*pw[n-i+1])%Mod;
            int tmp2=(ih[i+1]-ih[i+m+1]+Mod)%Mod; tmp2=(tmp2*pw[i])%Mod;
            if(tmp1==tmp2) k=m, s=m+1;
            else e=m-1;
        }
        c[s[i-1]-'a'+1]++;
        if(k) vec[s[i-1]-'a'+1].emplace_back(i+1, i+k);
    }
    for(int i=0; i<=26; i++) f(vec[i], i>0), ans=max(ans, c[i]);
    cout<<ans;
    return 0;
}

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