Submission #1127600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127600		doducanh	Palinilap (COI16_palinilap)	C++20	100 / 100	105 ms	34192 KiB

palinilap

///roadtoVOI2025
///enjoythejourney
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int mod=1e9+9;
const int maxn=1e5+7;
string s;
int p[maxn];
int h[maxn];
int hn[maxn];
int mul(int a,int b)
{
    return (1ll*a*b)%mod;
}
int add(int a,int b)
{
    ll c=a+b;
    if(c>=mod)c-=mod;
    return c;
}
int sub(int a,int b)
{
    ll c=a-b;
    if(c<0)c+=mod;
    return c;
}
int get(int l,int r)
{
    return sub(h[r],mul(h[l-1],p[r-l+1]));
}
int getn(int l,int r)
{
    return sub(hn[l],mul(hn[r+1],p[r-l+1]));
}
int get(int l,int r,pair<int,int>nw)
{
    int pref=sub(h[r],mul(h[l-1],p[r-l+1]));
    if(nw.fi>=l&&nw.fi<=r){
        pref=sub(pref,mul(s[nw.fi]-'a',p[r-nw.fi]));
        pref=add(pref,mul(nw.se,p[r-nw.fi]));
    }
    return pref;
}
int getn(int l,int r,pair<int,int>nw){
    int pref=sub(hn[l],mul(hn[r+1],p[r-l+1]));
    if(nw.fi>=l&&nw.fi<=r){
        pref=sub(pref,mul(s[nw.fi]-'a',p[nw.fi-l]));
        pref=add(pref,mul(nw.se,p[nw.fi-l]));
    }
    return pref;
}
bool ispal(int l,int r)
{
    return (get(l,r)==getn(l,r));
}
bool ispalnw(int l,int r,pair<int,int>nw)
{
    return get(l,r,nw)==getn(l,r,nw);
}
void inp()
{
    cin>>s;
}
int tknp(int lo,int hi,function<bool(int)>check)
{
    int res=-1;
    while(lo<=hi){
        int m=(lo+hi)/2;
        if(check(m)){
            res=m;
            lo=m+1;
        }
        else hi=m-1;
    }
    return res;
}
int good[maxn][30];
vector<int>getval(int n,const vector<ii>&val)
{
    vector<int>tmp;
    tmp.resize(n+1);
    for(ii pp:val){
        tmp[pp.fi]++;
        tmp[pp.se+1]--;
    }
    for(int i=1;i<tmp.size();i++){
        tmp[i]+=tmp[i-1];
    }
    for(ii pp:val){
        tmp[pp.se+1]-=(pp.se+1-pp.fi);
    }
    for(int i=1;i<tmp.size();i++){
        tmp[i]+=tmp[i-1];
    }
    tmp.pop_back();
    return tmp;
}
void sol()
{
    int n=s.size();
    s=' '+s;
    p[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=add(mul(h[i-1],101),s[i]-'a');
        p[i]=mul(p[i-1],101);
    }
    hn[n+1]=0;
    for(int i=n;i>=1;i--){
        hn[i]=add(mul(hn[i+1],101),s[i]-'a');
    }
    function<bool(int)>check;
    vector<ii>removals1;
    ll sum=0;
    vector<ii>removals2;
    vector<pair<int,int>>diff;
    for(int i=1;i<=n;i++){
        int most=min(i-1,n-i);
        check=[&](int x){
            return ispal(i-x,i+x);
        };
        int rawpal=tknp(0,most,check);
        sum+=rawpal+1;
        pair<int,int> nw={i+rawpal+1,s[i-rawpal-1]-'a'};
        check=[&](int x){
            return ispalnw(i-x,i+x,nw);
        };
        if(rawpal!=0){
            removals1.push_back({i-rawpal-1,i-1-1});
            removals2.push_back({i+1-1,i+rawpal-1});
        }
        int nwpal=tknp(rawpal+1,most,check);
        if(nwpal!=-1){
            good[i-rawpal-1][s[i+rawpal+1]-'a']+=nwpal-rawpal;
            good[i+rawpal+1][s[i-rawpal-1]-'a']+=nwpal-rawpal;
        }
        if (i < n) {
			most = min(i, n - i);
			check = [&](int d) { return ispal(i - d + 1, i + d); };
			int raw_pal = tknp(0, most, check);
			sum += raw_pal;
			if (raw_pal > 0) {
				removals1.push_back({i - raw_pal+1-1, i-1});
				removals2.push_back({i + 1-1, i + raw_pal-1});
			}
			pair<int, int> rep = {i + raw_pal + 1, s[i - raw_pal]-'a'};
			check = [&](int d) { return ispalnw(i - d + 1, i + d, rep); };
			int rep_pal = tknp(raw_pal + 1, most, check);
			if (rep_pal != -1) {
				good[rep.first][rep.second] += rep_pal - raw_pal;
				good[i - raw_pal][s[i + raw_pal + 1]-'a'] += rep_pal - raw_pal;
			}
		}
    }
    ll res=0;
    res=sum;
    for(ii &tmp:removals2){

        tmp={n-tmp.se-1,n-tmp.fi-1};
    }

    vector<int>bad1=getval(n,removals1);
    vector<int>bad2=getval(n,removals2);
    reverse(bad2.begin(),bad2.end());
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++){
            res=max(res,sum-bad1[i-1]-bad2[i-1]+good[i][j]);
        }
    }
    cout<<res;
}
signed main(void)
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    inp();
    sol();
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 46 / 46