oj.uz

Submission #52035

# Submission time Handle Problem Language Result Execution time Memory
52035 2018-06-23T10:35:30 Z Milki Palinilap (COI16_palinilap) C++14
100 / 100
 116 ms 27948 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> point;

const ll MAXN = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll BAZA = 1307;

string s;
int h[MAXN], h_[MAXN], pot[MAXN];

void calcHash(){
    pot[0] = 1;
    h[0] = s[0];

    FOR(i, 1, (int)s.size()){
        h[i] = ((ll)h[i - 1] * BAZA + s[i]) % MOD;
        pot[i] = (ll)pot[i - 1] * BAZA % MOD;
    }

    h_[0] = s[s.size() - 1];
    for(int i = s.size() - 2, cnt = 1; i >= 0; --i, ++cnt)
        h_[cnt] = ((ll)h_[cnt - 1] * BAZA + s[i]) % MOD;
}

ll calc(ll x, ll y){
    ll k = 0;
    if(x) k = (ll)h[x - 1] * pot[y] % MOD;
    return ((((ll)h[x + y - 1] - k) % MOD) + MOD) % MOD;
}

ll calc_(ll x, ll y){
    ll k = 0;
    if(x) k = (ll)h_[x - 1] * pot[y] % MOD;
    return ((((ll)h_[x + y - 1] - k) % MOD) + MOD) % MOD;
}

ll cntDec[MAXN];
ll decrease[MAXN];
ll increase[MAXN], letInc[MAXN][30];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0),

    cin >> s;

    calcHash();
    ll sol = 0;

    int len = (int)s.size();

    REP(i, len){
        //neparni
        ll lo = 1, hi = min(i + 1, len - i);
        while(lo < hi){
            ll mid = (lo + hi + 1) >> 1;

            if(calc(i, mid) == calc_(len - i - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        cntDec[i - lo + 1] ++;
        cntDec[i + 1] -= 2;
        cntDec[i + lo + 1] ++;

        sol += lo;
        increase[i] += lo;

        ll jump = lo + 1;
        lo = 0, hi = min(i + 1, len - i) - jump;

        while(lo < hi){
            ll mid = (lo + hi + 1) >> 1;

            if(calc(i + jump, mid) == calc_(len - i + jump - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }
        if(i + jump - 1 >= 0 && i - jump + 1 >= 0){
            letInc[i + jump - 1][s[i - jump + 1] - 'a'] += lo + 1;
            letInc[i - jump + 1][s[i + jump - 1] - 'a'] += lo + 1;
        }
        if(i == len - 1) continue;
        //neparni
        lo = 0, hi = max(0, min(i + 1, len - i - 1));
        while(lo < hi){
            ll mid = (lo + hi + 1) >> 1;

            if(calc(i + 1, mid) == calc_(len - i - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        sol += lo;

        if(lo){
            cntDec[i - lo + 1] ++;
            cntDec[i + 1] --;
            cntDec[i + 2] --;
            cntDec[i + lo + 2] ++;
        }

        jump = lo + 1;
        lo = 0, hi = max(0LL, min(i + 1, len - i - 1) - jump);
        while(lo < hi){

            ll mid = (lo + hi + 1) >> 1;

            if(calc(i + jump + 1, mid) == calc_(len - i + jump - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }
        if(i + jump >= 0 && i - jump + 1 >= 0){
            letInc[i + jump][s[i - jump + 1] - 'a'] += lo + 1;
            letInc[i - jump + 1][s[i + jump] - 'a'] += lo + 1;
        }
    }

    ll cnt = 0, curr = 0;

    REP(i, len){
        cnt += cntDec[i];
        curr += cnt;
        decrease[i] = curr;
    }

    ll best = 0;
    REP(i, len)
        REP(j, 26){
            best = max(best, increase[i] + letInc[i][j] - decrease[i]);

        }

    cout << sol + best;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 524 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1932 KB Output is correct
2 Correct 5 ms 1960 KB Output is correct
3 Correct 6 ms 1960 KB Output is correct
4 Correct 4 ms 1960 KB Output is correct
5 Correct 5 ms 1960 KB Output is correct
6 Correct 6 ms 1960 KB Output is correct
7 Correct 6 ms 1960 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 27840 KB Output is correct
2 Correct 81 ms 27848 KB Output is correct
3 Correct 85 ms 27884 KB Output is correct
4 Correct 104 ms 27948 KB Output is correct
5 Correct 103 ms 27948 KB Output is correct
6 Correct 104 ms 27948 KB Output is correct
7 Correct 105 ms 27948 KB Output is correct
8 Correct 67 ms 27948 KB Output is correct
9 Correct 105 ms 27948 KB Output is correct
10 Correct 105 ms 27948 KB Output is correct
11 Correct 80 ms 27948 KB Output is correct
12 Correct 116 ms 27948 KB Output is correct
13 Correct 112 ms 27948 KB Output is correct
14 Correct 108 ms 27948 KB Output is correct
15 Correct 104 ms 27948 KB Output is correct
16 Correct 100 ms 27948 KB Output is correct
17 Correct 101 ms 27948 KB Output is correct
18 Correct 104 ms 27948 KB Output is correct
19 Correct 111 ms 27948 KB Output is correct