oj.uz

Submission #51974

# Submission time Handle Problem Language Result Execution time Memory
51974 2018-06-22T19:34:23 Z Milki Palinilap (COI16_palinilap) C++11
54 / 100
 125 ms 55096 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 = 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(i + mid - 1 >= s.size() || len - i - 1 + mid - 1 >= s.size()){
                assert(s.size() == 0);
            }*/

            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(i + jump + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
                assert(s.size() == 0);
            }*/
            if(calc(i + jump, mid) == calc_(len - i + jump - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        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 = min(i + 1, len - i - 1);
        while(lo < hi){
            ll mid = (lo + hi + 1) >> 1;
            /*if(i + 1 + mid - 1 >= s.size() || len - i - 1 - mid + 1 >= s.size()){
                assert(s.size() == 0);
            }*/
            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 = min(i + 1, len - i - 1) - jump;
        while(lo < hi){

            ll mid = (lo + hi + 1) >> 1;
            /*if(i + jump + 1 + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
                assert(s.size() == 0);
            }*/
            if(calc(i + jump + 1, mid) == calc_(len - i + jump - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        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 3 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct

Subtask #2
37.0 / 37.0

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

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 27756 KB Output is correct
2 Correct 83 ms 27944 KB Output is correct
3 Correct 83 ms 27944 KB Output is correct
4 Correct 99 ms 27944 KB Output is correct
5 Correct 100 ms 27944 KB Output is correct
6 Correct 98 ms 27944 KB Output is correct
7 Runtime error 125 ms 55096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -