oj.uz

Submission #752818

# Submission time Handle Problem Language Result Execution time Memory
752818 2023-06-04T01:40:44 Z winter0101 Palindromes (APIO14_palindrome) C++14
100 / 100
 740 ms 61456 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 12 ms 21412 KB Output is correct
3 Correct 12 ms 21444 KB Output is correct
4 Correct 12 ms 21448 KB Output is correct
5 Correct 12 ms 21400 KB Output is correct
6 Correct 12 ms 21460 KB Output is correct
7 Correct 13 ms 21388 KB Output is correct
8 Correct 12 ms 21476 KB Output is correct
9 Correct 12 ms 21460 KB Output is correct
10 Correct 12 ms 21436 KB Output is correct
11 Correct 12 ms 21460 KB Output is correct
12 Correct 13 ms 21364 KB Output is correct
13 Correct 12 ms 21460 KB Output is correct
14 Correct 13 ms 21480 KB Output is correct
15 Correct 12 ms 21452 KB Output is correct
16 Correct 13 ms 21436 KB Output is correct
17 Correct 12 ms 21464 KB Output is correct
18 Correct 13 ms 21460 KB Output is correct
19 Correct 12 ms 21460 KB Output is correct
20 Correct 15 ms 21432 KB Output is correct
21 Correct 12 ms 21460 KB Output is correct
22 Correct 12 ms 21464 KB Output is correct
23 Correct 12 ms 21444 KB Output is correct
24 Correct 12 ms 21476 KB Output is correct
25 Correct 12 ms 21460 KB Output is correct
26 Correct 13 ms 21480 KB Output is correct
27 Correct 13 ms 21456 KB Output is correct
28 Correct 13 ms 21460 KB Output is correct
29 Correct 12 ms 21460 KB Output is correct
30 Correct 15 ms 21468 KB Output is correct
31 Correct 13 ms 21460 KB Output is correct
32 Correct 12 ms 21460 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 12 ms 21460 KB Output is correct
3 Correct 12 ms 21588 KB Output is correct
4 Correct 14 ms 21516 KB Output is correct
5 Correct 13 ms 21588 KB Output is correct
6 Correct 15 ms 21588 KB Output is correct
7 Correct 13 ms 21460 KB Output is correct
8 Correct 13 ms 21516 KB Output is correct
9 Correct 13 ms 21460 KB Output is correct
10 Correct 13 ms 21460 KB Output is correct
11 Correct 12 ms 21468 KB Output is correct
12 Correct 13 ms 21468 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22484 KB Output is correct
2 Correct 24 ms 22364 KB Output is correct
3 Correct 28 ms 22892 KB Output is correct
4 Correct 27 ms 22756 KB Output is correct
5 Correct 26 ms 22100 KB Output is correct
6 Correct 22 ms 22188 KB Output is correct
7 Correct 22 ms 22220 KB Output is correct
8 Correct 17 ms 21988 KB Output is correct
9 Correct 20 ms 21972 KB Output is correct
10 Correct 21 ms 22288 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 31764 KB Output is correct
2 Correct 147 ms 30408 KB Output is correct
3 Correct 236 ms 34796 KB Output is correct
4 Correct 217 ms 33264 KB Output is correct
5 Correct 187 ms 28460 KB Output is correct
6 Correct 149 ms 28660 KB Output is correct
7 Correct 153 ms 30048 KB Output is correct
8 Correct 76 ms 27384 KB Output is correct
9 Correct 121 ms 28880 KB Output is correct
10 Correct 166 ms 29716 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 52428 KB Output is correct
2 Correct 463 ms 45724 KB Output is correct
3 Correct 726 ms 61456 KB Output is correct
4 Correct 664 ms 52956 KB Output is correct
5 Correct 675 ms 43428 KB Output is correct
6 Correct 582 ms 46476 KB Output is correct
7 Correct 623 ms 47144 KB Output is correct
8 Correct 229 ms 38956 KB Output is correct
9 Correct 217 ms 38940 KB Output is correct
10 Correct 740 ms 46300 KB Output is correct
11 Correct 499 ms 48228 KB Output is correct
12 Correct 425 ms 40548 KB Output is correct