Submission #309854

#	Time	Username	Problem	Language	Result	Execution time	Memory
309854		qiangbao	Palinilap (COI16_palinilap)	C++98	100 / 100	84 ms	25852 KiB

palinilap

#include <iostream>

using namespace std;

typedef long long ll;

const ll P=31;
const ll MOD=1000000007;

ll n;
string s;

ll inc[100001][27];
ll decr[100001];
ll add[100001];

ll hs[100005];
ll hs2[100005];

ll ans=0;
ll best=0;

ll powp[100005];

void bd()
{
    ll i;
    
    for(i=1;i<=n;i++)
        hs[i]=(hs[i-1]+(s[i-1]-'a'+1)*powp[i-1])%MOD;
    for(i=n;i>=1;i--)
        hs2[i]=(hs2[i+1]+(s[i-1]-'a'+1)*powp[n-i])%MOD;
}

ll get(ll x, ll y, ll wch)
{
    if(wch==1)
        return ((hs[y]-hs[x-1]+MOD)*powp[n-y])%MOD;
    else
        return ((hs2[x]-hs2[y+1]+MOD)*powp[x-1])%MOD;
}

ll ok(ll x, ll aa, ll bb)
{
    if(aa-x<=0 || bb+x>n || get(aa-x, aa, 1)!=get(bb, bb+x, 2))
        return 0;
    return 1;
}

void wk2(int aa, int bb)
{
    ll lo=0, hi=n+1, m;
    while(lo<hi){
        m=(lo+hi)/2;
        if(ok(m, aa, bb))
            lo=m+1;
        else
            hi=m;
    }
    lo--;
    ans+=lo+1;
    if(aa==bb)
        decr[aa]-=lo+1;
    if(lo>=0){
        if(aa==bb)
            add[aa-lo]++, add[bb+1]-=2, add[bb+lo+2]++;
        else
            add[aa-lo]++, add[bb]--, add[bb+1]--, add[bb+lo+2]++;
    }
        
    if(aa-lo-1<=0 || bb+lo+1>=n+1)
        return;
    
    ll kp=lo;
    lo=0, hi=n+1;
    while(lo<hi){
        m=(lo+hi)/2;
        if(ok(m, aa-kp-2, bb+kp+2))
            lo=m+1;
        else
            hi=m;
    }
    inc[aa-kp-1][s[bb+kp]-'a'+1]+=lo+1;
    inc[bb+kp+1][s[aa-kp-2]-'a'+1]+=lo+1;
}

void ini()
{
    ll i;
    
    powp[0]=1;
    for(i=1;i<=100004;i++)
        powp[i]=powp[i-1]*P, powp[i]%=MOD;
}

void wk()
{
    ll i;
    
    ini();
    bd();
    
    for(i=1;i<=n;i++){
        wk2(i, i);
        if(i!=n)
            wk2(i, i+1);
    }
    
    ll add2=0;
    for(i=1;i<=n;i++)
        add2+=add[i], add[i]=add2;
    add2=0;
    for(i=1;i<=n;i++)
        add2+=add[i], decr[i]+=add2;
    
}

int main()
{
    ios_base:: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    ll i, j;
    
    cin >> s, n=s.length();
    
    wk();
    for(i=0;i<n;i++){
        ll f=s[i]-'a'+1;
        for(j=1;j<=26;j++){
            if(j==f)
                continue;
            best=max(best, inc[i+1][j]-decr[i+1]);
        }
    }
    
    cout << ans+best << endl;

    return 0;
}

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