oj.uz

Submission #418082

# Submission time Handle Problem Language Result Execution time Memory
418082 2021-06-05T04:52:55 Z SirCovidThe19th Palinilap (COI16_palinilap) C++14
100 / 100
 216 ms 27240 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second

const int mx = 1e5+5, p = 5281, m1 = 1e9+7, m2 = 1e9+9;

int n; string str; 
pair<ll, ll> pPow[mx], hsh[2][mx]; 
ll create[mx][26]; pair<ll, ll> destroy[mx]; ll ans;
//hsh is 1 indexed, getHash is inclusive, getReach is inclusive(0 means invalid)
pair<ll, ll> getHash(int l, int g, int rev){
    l++; g++; int dir[2] = {-1, 1}; if (rev == 1) swap(l, g); l += dir[rev];
    return {((hsh[rev][g].f-(hsh[rev][l].f*pPow[abs(g-l)].f)%m1)+m1)%m1, 
            ((hsh[rev][g].s-(hsh[rev][l].s*pPow[abs(g-l)].s)%m2)+m2)%m2};
}
int getReach(int l, int r){
    int low = 0, high = min(l+1, n-r);
    while (low < high){
        int mid = (low+high+1)/2;
        if (getHash(l-mid+1, l, 0) == getHash(r, r+mid-1, 1)) low = mid;
        else high = mid-1;
    }
    return low;
}
int main() {
    cin >> str; n = str.size(); pPow[0] = {1, 1};
    for (int i = 0; i < n; i++){
        hsh[0][i+1] = {(hsh[0][i].f*p+(str[i]-'a'+1))%m1, (hsh[0][i].s*p+(str[i]-'a'+1))%m2};
        hsh[1][n-i] = {(hsh[1][n-i+1].f*p+(str[n-i-1]-'a'+1))%m1, (hsh[1][n-i+1].s*p+(str[n-i-1]-'a'+1))%m2}; 
        pPow[i+1] = {(pPow[i].f*p)%m1, (pPow[i].s*p)%m2};
    }
    for (int i = 0; i < n; i++){
        for (int j = i; j < i+2; j++){
            int r = getReach(i, j); ans += r;
            if (i-r >= 0 and j+r <= n){
                int add = 1+getReach(i-r-1, j+r+1);
                create[i-r][str[j+r]-'a'] += add; 
                create[j+r][str[i-r]-'a'] += add;
            }
            if (r > 0){
                destroy[i-r+1].f++; destroy[j+r].f++; 
                destroy[i-r+1].s -= i-r; destroy[j+r].s -= j+r;
                destroy[j].f--; destroy[i+1].f--;
                destroy[j].s += i-r, destroy[i+1].s += j+r; 
            }
        }
    }
    ll change = 0, rem = 0, best = 0;
    for (int i = 0; i < n; i++){
        change += destroy[i].f; rem += destroy[i].s;
        for (int j = 0; j < 26; j++) 
            best = max(best, create[i][j]-(i*change+rem));
    }
    cout<<ans+best;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1612 KB Output is correct
2 Correct 6 ms 1580 KB Output is correct
3 Correct 8 ms 1584 KB Output is correct
4 Correct 5 ms 1068 KB Output is correct
5 Correct 6 ms 1356 KB Output is correct
6 Correct 8 ms 1612 KB Output is correct
7 Correct 8 ms 1612 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 27100 KB Output is correct
2 Correct 140 ms 27240 KB Output is correct
3 Correct 151 ms 27200 KB Output is correct
4 Correct 199 ms 27080 KB Output is correct
5 Correct 203 ms 27116 KB Output is correct
6 Correct 201 ms 27116 KB Output is correct
7 Correct 200 ms 27144 KB Output is correct
8 Correct 115 ms 27164 KB Output is correct
9 Correct 211 ms 27204 KB Output is correct
10 Correct 203 ms 27112 KB Output is correct
11 Correct 152 ms 27160 KB Output is correct
12 Correct 216 ms 27100 KB Output is correct
13 Correct 213 ms 27164 KB Output is correct
14 Correct 198 ms 27096 KB Output is correct
15 Correct 205 ms 27224 KB Output is correct
16 Correct 172 ms 27204 KB Output is correct
17 Correct 195 ms 27156 KB Output is correct
18 Correct 203 ms 27204 KB Output is correct
19 Correct 195 ms 27092 KB Output is correct