Submission #752818

#	Time	Username	Problem	Language	Result	Execution time	Memory
752818		winter0101	Palindromes (APIO14_palindrome)	C++14	100 / 100	740 ms	61456 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
using pil=pair<int,long long>;
struct SA{
int n;
string s;
vector<int>pos,tmp,lcp,sa;
void build(){
for1(i,0,n-1)pos[i]=s[i],sa[i]=i;
for(int gap=1;;gap*=2){
    auto cmp=[&](int i,int j){
    if (pos[i]!=pos[j])return pos[i]<pos[j];
    i+=gap;
    j+=gap;
    if (i<n&&j<n)return pos[i]<pos[j];
    return i>j;
    };
    sort(all(sa),cmp);
    for1(i,0,n-2)tmp[i+1]=tmp[i]+cmp(sa[i],sa[i+1]);
    for1(i,0,n-1)pos[sa[i]]=tmp[i];
    if (tmp[n-1]==n-1)break;
}
}
void buildLCP(){
for1(i,0,n-1){
if (pos[i]==n-1)continue;
int diff=0;
if (i>0){
    diff=max(diff,lcp[pos[i-1]]-1);
}
int j=sa[pos[i]+1];
while (i+diff<n&&j+diff<n&&s[i+diff]==s[j+diff])diff++;
lcp[pos[i]]=diff;
}
}
void resz(string S){
s=S;
n=sz(s);
pos.resize(n);
tmp.resize(n);
sa.resize(n);
lcp.resize(n);
build();
buildLCP();
}
};
struct hashing{
vector<long long>pw,h,rh;
long long base,du;
void build(string s){
base=311;
du=998244353;
int n=sz(s);
pw.resize(n+1);
h.resize(n+1);
rh.resize(n+2);
pw[0]=1;
for1(i,1,n)pw[i]=(1ll*pw[i-1]*base)%du;
for1(i,1,n)h[i]=(1ll*h[i-1]*base+s[i-1]-'a'+1)%du;
for2(i,n,1){
rh[i]=(1ll*rh[i+1]*base+s[i-1]-'a'+1)%du;
}
}
long long get(int i,int j){
i++;
j++;
return (1ll*h[j]-1ll*h[i-1]*pw[j-i+1]+1ll*du*du)%du;
}
long long rget(int i,int j){
i++;
j++;
return (1ll*rh[i]-1ll*rh[j+1]*pw[j-i+1]+1ll*du*du)%du;
}
};
const int maxn=3e5+8;
vector<int>d1[maxn],d2[maxn],c[maxn];
int best[maxn],f[maxn];
bool turn[maxn];
long long ans=1;
int findset(int u){
if (f[u]<0)return u;
return f[u]=findset(f[u]);
}
void unite(int u,int v){
u=findset(u),v=findset(v);
if (u==v)return;
if (f[u]>f[v])swap(u,v);
f[u]+=f[v];
f[v]=u;
}
int cc(int u){
u=findset(u);
return abs(f[u]);
}
int cnt[26];
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("usaco.INP","r",stdin);
    //freopen("usaco.OUT","w",stdout);
    string s;
    cin>>s;
    int n=sz(s);
    SA a;
    a.resz(s);
    hashing b;
    b.build(s);
    for (auto v:s)cnt[v-'a']++;
    //for1(i,0,25)cout<<i<<" "<<cnt[i]<<'\n';
    set<int>t1,t2;
    set<int>::iterator it;
    //cerr<<b.get(1,2)<<" "<<b.rget(4,5);
    for2(i,n-1,0){
    if (a.pos[i]!=n-1){
        if (a.lcp[a.pos[i]]>0){
            best[i]=1;
        }
    }
    int l=1,r=min(i,n-(i+1)),p1=0;
    while (l<=r){
        int mid=(l+r)/2;
        //cerr<<mid<<'\n';
        if (b.get(i-mid,i-1)==b.rget(i+1,i+mid)){
            p1=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    if (p1>0){
        ans=max(ans,1ll+p1*2);
        d1[i-p1].pb(i-1);
        t1.insert(i-1);
    }
    if (i+1<n&&s[i]==s[i+1]){
        l=2,r=min(i+1,n-1-(i+1)+1),p1=1;
        while (l<=r){
            int mid=(l+r)/2;
            if (b.get(i-mid+1,i)==b.rget(i+1,i+1+mid-1)){
                p1=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        t2.insert(i);
        ans=max(ans,1ll*2*p1);
        //cerr<<i<<" "<<i-p1+1<<'\n';
        //if (i==73)cerr<<p1<<'\n';
        d2[i-p1+1].pb(i);
    }
    if (!t1.empty()){
        it=t1.end();
        it--;
        if (*it>=i){
        ans=max(ans,1ll+(*it-i+1)*2);
        }
        if (a.pos[i]!=n-1){
        int sz=a.lcp[a.pos[i]]/2;
        if (sz*2==a.lcp[a.pos[i]])sz--;
        it=t1.upper_bound(i+sz-1);
        if (it!=t1.begin()){
        it--;
        best[i]=max(best[i],(*it-i+1)*2+1);
        //cerr<<i<<" "<<best[i]<<'\n';
        }
        }
    }
    if (!t2.empty()){
        it=t2.end();
        it--;
        ans=max(ans,1ll*2*(*it-i+1));
        //cerr<<i<<" "<<*it<<" "<<*it-i+1<<'\n';
        if (a.pos[i]!=n-1){
        int sz=a.lcp[a.pos[i]]/2;
        it=t2.upper_bound(i+sz-1);
        if (it!=t2.begin()){
        it--;
        //if (i==49)cerr<<*it<<'\n';
        best[i]=max(best[i],(*it-i+1)*2);
        }
        }
    }
    for(auto v:d1[i]){
        t1.erase(v);
    }
    for(auto v:d2[i]){
        //cerr<<i<<" "<<v<<'\n';
        //if (v==73)cerr<<i<<'\n';
        t2.erase(v);
    }
    //cout<<i<<" "<<lc<<'\n';
    }
    for1(i,0,n-2){
        f[i]=-1;
        c[a.lcp[i]].pb(i);
        //cout<<a.sa[i]<<'\n';
        //cout<<ia.lcp[i]<<'\n';
    }
    for2(i,n,1){
    for (auto v:c[i]){
        if (v>0&&turn[v-1]){
            unite(v,v-1);
        }
        if (v+1<n-1&&turn[v+1]){
            unite(v,v+1);
        }
        ans=max(ans,1ll*(cc(v)+1)*best[a.sa[v]]);
        turn[v]=1;
        //if (i==1)cout<<best[a.sa[v]]<<" "<<cc(v)+1<<'\n';
    }
    }
    cout<<ans;
}

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