oj.uz

Submission #309854

# Submission time Handle Problem Language Result Execution time Memory
309854 2020-10-04T17:35:33 Z qiangbao Palinilap (COI16_palinilap) C++
100 / 100
 84 ms 25852 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2432 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Correct 4 ms 2432 KB Output is correct
4 Correct 3 ms 1920 KB Output is correct
5 Correct 4 ms 2176 KB Output is correct
6 Correct 5 ms 2432 KB Output is correct
7 Correct 4 ms 2324 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 25728 KB Output is correct
2 Correct 70 ms 25756 KB Output is correct
3 Correct 70 ms 25720 KB Output is correct
4 Correct 72 ms 25720 KB Output is correct
5 Correct 71 ms 25720 KB Output is correct
6 Correct 69 ms 25720 KB Output is correct
7 Correct 70 ms 25852 KB Output is correct
8 Correct 41 ms 4668 KB Output is correct
9 Correct 68 ms 25720 KB Output is correct
10 Correct 68 ms 25724 KB Output is correct
11 Correct 62 ms 25720 KB Output is correct
12 Correct 74 ms 25812 KB Output is correct
13 Correct 81 ms 25720 KB Output is correct
14 Correct 69 ms 25720 KB Output is correct
15 Correct 70 ms 25720 KB Output is correct
16 Correct 83 ms 25720 KB Output is correct
17 Correct 84 ms 25720 KB Output is correct
18 Correct 72 ms 25720 KB Output is correct
19 Correct 68 ms 25724 KB Output is correct