Submission #1076904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076904		jcelin	Palinilap (COI16_palinilap)	C++14	100 / 100	195 ms	43940 KiB

palinilap

#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()
 
const int MOD = 1e9 + 7, mxn = 1e5 + 10;
 
ll n, a[mxn];
 
struct SegmentTree {
    vector<ll> sum;
    vector<pair<ll, ll>> lz;
  
    SegmentTree(int n) {
        sum.resize(4 * n);
        lz.resize(4 * n);
    }
  
    void push(int k, int l, int r) {
        if (lz[k].second) {
            ll sz = (r - l + 1);
            sum[k] += lz[k].first * sz;
            sum[k] += lz[k].second * (sz * (sz + 1) / 2);
            if (l != r) {
                lz[k * 2].first += lz[k].first;
                lz[k * 2].second += lz[k].second;
                ll mid = (l + r) / 2;
                lz[k * 2 + 1].first += lz[k].first + lz[k].second * (mid - l + 1);
                lz[k * 2 + 1].second += lz[k].second;
            }
            lz[k] = {0, 0};
        }
    }
  
    void update(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return;
        if (i <= l && r <= j) {
            lz[k].first += l - i;
            lz[k].second += 1;
            push(k, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(k * 2, l, mid, i, j);
        update(k * 2 + 1, mid + 1, r, i, j);
    }
  
    void get(int k, int l, int r, bool d) {
        push(k, l, r);
        if (l == r) {
            if (d) a[l] += sum[k];
            else a[n - l - 1] += sum[k];
            return;
        }
        int mid = (l + r) / 2;
        get(k * 2, l, mid, d);
        get(k * 2 + 1, mid + 1, r, d);
    }
} sgtF(mxn), sgtB(mxn);
 
  
ll expo(ll a, ll b, ll mod) {
    a %= mod;
    ll res = 1;
    while (b) {
        if (b % 2 == 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return res;
}
 
ll fact[mxn + 1], inv[mxn + 1], inv29 = expo(29, MOD - 2, MOD);
  
void precalc() {
    inv[0] = expo(1, MOD - 2, MOD);
    for (int i = 1; i <= mxn; i++) inv[i] = (inv[i - 1] * inv29) % MOD;
}
 
string s;
ll prf[mxn], suf[mxn], F[mxn], change[mxn][26];
 
ll getPRF(int l, int r) {
    ll num = prf[r] - (l ? prf[l - 1] : 0);
    num = (num + MOD) % MOD;
    num = (num * inv[l]) % MOD;
    return num;
}
 
ll getSUF(int l, int r) {
    ll num = suf[l] - (r < n - 1 ? suf[r + 1] : 0);
    num = (num + MOD) % MOD;
    num = (num * inv[n - 1 - r]) % MOD;
    return num;
}
 
bool same(int l1, int r1, int l2, int r2) {
    if (l1 < 0 || r1 >= n || l2 < 0 || r2 >= n) return 0;
    return getPRF(l1, r1) == getSUF(l2, r2);
}
 
ll solve(ll i, int startL = -1000, int startR = -1000) {
    int sl = i / 2, sr = i / 2;
    if (i % 2 != 0) sr = i / 2 + 1;
    if (startL != -1000) {
        sl = startL;
        sr = startR;
    }
    if (sl < 0 || sr >= n) return 0; 
    int l = 0, r = min(i / 2, n - i / 2) + 2;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (same(sl - mid, sl, sr, sr + mid)) l = mid;
        else r = mid;
    }
    return l;
}
 
void updateF(int l, int r) {
    if (l > r) return;
    sgtF.update(1, 0, n - 1, l, r);
}
 
void updateB(int l, int r) {
    if (n - r - 1 > n - l - 1) return;
    sgtB.update(1, 0, n - 1, n - r - 1, n - l - 1);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precalc();
    cin >> s;
    n = s.size();
    F[0] = 1;
    for (int i = 1; i <= n; i++) F[i] = (F[i - 1] * 29) % MOD;
    for (int i = 0; i < n; i++) {
        if (i) prf[i] = prf[i - 1];
        prf[i] = (prf[i] + (s[i] - 'a') * F[i]) % MOD;
    }
    for (int i = n - 1; i >= 0; i--) {
        if (i < n - 1) suf[i] = suf[i + 1];
        suf[i] = (suf[i] + (s[i] - 'a') * F[n - 1 - i]) % MOD;
    }
    ll ans = 0;
    for (int i = 0; i < 2 * n - 1; i++) {
        int sl = i / 2, sr = i / 2;
        if (i % 2 != 0) sr = i / 2 + 1;
        ll add = s[sl] == s[sr];
        ll lp = solve(i) + add;
        int LR = sl - (lp - 1), RR = sr + (lp - 1);
        ans += lp;
        if (LR != RR) {
            updateF(LR, sl - (i % 2 == 0));
            updateB(sr + (sl == sr), RR);
        }
        int L = sl - lp, R = sr + lp; 
        if (L < 0 || R > n - 1) continue;
        ll newLp = solve(i, L - 1, R + 1);
        if (L - 1 - newLp >= 0 && R + 1 + newLp < n && s[L - 1 - newLp] == s[R + 1 + newLp]) add = 1;
        else add = 0;
        change[L][s[R] - 'a'] += newLp + 1 + add;
        newLp = solve(i, L - 1, R + 1);
        if (L - 1 - newLp >= 0 && R + 1 + newLp < n && s[L - 1 - newLp] == s[R + 1 + newLp]) add = 1;
        else add = 0;
        change[R][s[L] - 'a'] += newLp + 1 + add;
    }
    sgtF.get(1, 0, n - 1, 1);
    sgtB.get(1, 0, n - 1, 0);
    ll mx = 0;
    for (int i = 0; i < n; i++) {
        ll best = 0;
        for (int j = 0; j < 26; j++) best = max(best, change[i][j]);
        mx = max(mx, best - a[i]);
    }
    cout << ans + mx;
}

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 46 / 46