oj.uz

Submission #655906

# Submission time Handle Problem Language Result Execution time Memory
655906 2022-11-06T03:03:54 Z gozonite Palinilap (COI16_palinilap) C++14
100 / 100
 323 ms 26576 KB 
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
#include <iomanip>
#include <random>
using namespace std;
using ll = long long;
ll M = 1e9 + 7, P = 31;

string s;
int n;
ll power[100000][26]={}; // how many new palindromes can be made if index i is changed to char c in power[i][c]
ll rsum[100000]={}, lsum[100000]={}, rsump[100000]={}, lsump[100000]={};
ll P2[100000];
ll hpref[100000], hsuff[100000];

ll get_hash(int a, int b) {
    if (a == 0) return hpref[b];
    return ((hpref[b] - P2[b-a+1]*hpref[a-1])%M + M) % M;
}
ll rev_hash(int a, int b) {
    if (b == n-1) return hsuff[a];
    return ((hsuff[a] - P2[b-a+1]*hsuff[b+1])%M + M) % M;
}

ll add(int ctr, bool even) { //cout << "eval: " << ctr << " " << even << endl;
    ll res = 0;
    int lc = ctr, rc = ctr + even;

    int lo = 0, hi = min(lc+1, n-rc);
    while (lo < hi) {
        int mid = (lo+hi+1)/2;
        if (get_hash(rc, rc+mid-1) == rev_hash(lc-mid+1, lc)) lo = mid;
        else hi = mid-1;
    }
    res += lo;
    if (lc+1 < n) {
        rsum[lc+1] += lo + (even ? 0 : -1), rsump[lc+1]++;
        if (rc+lo < n) rsump[rc+lo]--;
    }
    if (rc-1 >= 0) {
        lsum[rc-1] += lo + (even ? 0 : -1), lsump[rc-1]++;
        if (lc-lo >= 0) lsump[lc-lo]--;
    }

    ll val = lo;
    // cout << "value: " << val << endl;
    // update powers
    if (lc-val < 0 || rc+val >= n) return res;
    
    // update right end
    ll dc = s[lc-val]-s[rc+val];
    lo = val+1, hi = min(lc+1, n-rc);
    while (lo < hi) {
        int mid = (lo+hi+1)/2;
        ll rh = (get_hash(rc, rc+mid-1) + dc*P2[mid-1-val] + (M<<5LL)) % M;
        ll lh = rev_hash(lc-mid+1, lc);
        if (rh == lh) lo = mid;
        else hi = mid-1;
    }
    power[rc+val][s[lc-val]-'a'] += lo-val;
    // cout << "rval: " << power[rc+val][s[lc-val]-'a'] << endl;

    // update left end
    dc = s[rc+val]-s[lc-val];
    lo = val+1, hi = min(lc+1, n-rc);
    while (lo < hi) {
        int mid = (lo+hi+1)/2;
        ll rh = get_hash(rc, rc+mid-1);
        ll lh = (rev_hash(lc-mid+1, lc) + dc*P2[mid-1-val] + (M<<5LL)) % M;
        //cout << "left bs: " << mid << " " << rh << " " << lh << endl;
        if (rh == lh) lo = mid;
        else hi = mid-1;
    }
    //cout << "updated left end: " << dc << " " << lo << endl;

    power[lc-val][s[rc+val]-'a'] += lo-val;
    // cout << "lval: " << power[lc-val][s[rc+val]-'a'] << endl;

    return res;
}

int main() {
    cin >> s;
    n = s.size();
    P2[0] = 1;
    for (int i = 1; i < n; i++) P2[i] = P2[i-1] * P % M;
    hpref[0] = s[0]-'a', hsuff[n-1] = s[n-1]-'a';
    for (int i = 1; i < n; i++) hpref[i] = (hpref[i-1]*P + ll(s[i]-'a')) % M;
    for (int i = n-2; i >= 0; i--) hsuff[i] = (hsuff[i+1]*P + ll(s[i]-'a')) % M;

    // cout << "Debugging forward and reverse hashes: " << endl;
    // cout << get_hash(3, 4) << " " << rev_hash(3, 4) << endl;

    ll ans = 0;
    // odd palindromes
    for (int i = 0; i < n; i++) {
        ans += add(i, 0);
        ans += add(i, 1);
    }
    // cout << "pre ans: " << ans << endl;
    // for (int i = 0; i < n; i++) cout << lsum[i] << " "; cout << endl;
    // for (int i = 0; i < n; i++) cout << rsum[i] << " "; cout << endl;
    // for (int i = 0; i < n; i++) cout << lsump[i] << " "; cout << endl;
    // for (int i = 0; i < n; i++) cout << rsump[i] << " "; cout << endl;
    
    ll ds = 0, cnt = 0;
    // carry out psums
    for (int i = 0; i < n; i++) {
        ds -= cnt;
        ds += rsum[i], cnt += rsump[i];
        rsum[i] = ds;
    }
    ds = 0, cnt = 0;
    for (int i = n-1; i >= 0; i--) {
        ds -= cnt;
        ds += lsum[i], cnt += lsump[i];
        lsum[i] = ds;
    }

    // cout << "Debugging new lsum, rsum, lsump, rsump: " << endl;
    // for (int i = 0; i < n; i++) cout << lsum[i] << " "; cout << endl;
    // for (int i = 0; i < n; i++) cout << rsum[i] << " "; cout << endl;

    ll dans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++) {
            dans = max(dans, power[i][j] - lsum[i] - rsum[i]);
        }
    }
    cout << ans+dans << endl;

}

Subtask #1
17.0 / 17.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1592 KB Output is correct
2 Correct 7 ms 1620 KB Output is correct
3 Correct 12 ms 1668 KB Output is correct
4 Correct 7 ms 1084 KB Output is correct
5 Correct 10 ms 1468 KB Output is correct
6 Correct 12 ms 1620 KB Output is correct
7 Correct 12 ms 1636 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 26376 KB Output is correct
2 Correct 155 ms 26404 KB Output is correct
3 Correct 178 ms 26436 KB Output is correct
4 Correct 309 ms 26348 KB Output is correct
5 Correct 316 ms 26384 KB Output is correct
6 Correct 309 ms 26408 KB Output is correct
7 Correct 313 ms 26400 KB Output is correct
8 Correct 93 ms 6120 KB Output is correct
9 Correct 314 ms 26336 KB Output is correct
10 Correct 309 ms 26392 KB Output is correct
11 Correct 154 ms 26372 KB Output is correct
12 Correct 323 ms 26412 KB Output is correct
13 Correct 296 ms 26436 KB Output is correct
14 Correct 313 ms 26408 KB Output is correct
15 Correct 308 ms 26316 KB Output is correct
16 Correct 221 ms 26380 KB Output is correct
17 Correct 305 ms 26496 KB Output is correct
18 Correct 315 ms 26428 KB Output is correct
19 Correct 305 ms 26576 KB Output is correct