Submission #895054

#	Time	Username	Problem	Language	Result	Execution time	Memory
895054		vjudge1	Palinilap (COI16_palinilap)	C++17	54 / 100	1020 ms	30296 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define F first
#define S second
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, unsigned long long>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define mp make_pair
#define debug cerr << "OK\n";

const int N = (int)1e5 + 5;
const ll mod = (int)1e9 + 9;
const ll mod1 = (int)1e9 + 9;
const ll inf = (int)1e9;
const ll INF = (ll)1e18;
const ll P = 31;

int n;
pll p[N], h[N], q[N];

pll mi(pll a) {
    return {(((-a.F) % mod) + mod) % mod, -a.S};
}

pll add(pll a, pll b) {
    return {(((a.F + b.F) % mod) + mod) % mod, a.S + b.S};
}

pll mul(pll a, pll b) {
    return {(a.F * b.F) % mod, a.S * b.S};
}

pll H(int l, int r) {
    return add(h[r], mi(mul(h[l - 1], p[r - l + 1])));
}

pll Q(int l, int r) {
    return add(q[r], mi(mul(q[l - 1], p[r - l + 1])));
}

bool ipal(int l1, int r1, int l2, int r2) {
    auto [L, R] = mp(n - r2 + 1, n - l2 + 1);
    return H(l1, r1) == Q(L, R);
}

ll us[N], uc[N], cs[N], sc[N], ch[N][27], tmp[N];

void solve() {
    string s;
    cin >> s;
    n = sz(s);
    string t = s;
    reverse(all(t));
    s = '#' + s;
    t = '#' + t;
    p[0] = {1, 1};
    for (int i = 1; i <= n; i++) {
        h[i].F = (h[i - 1].F * P + s[i] - 'a' + 1) % mod;
        h[i].S = (h[i - 1].S * P + s[i] - 'a' + 1);

        q[i].F = (q[i - 1].F * P + t[i] - 'a' + 1) % mod;
        q[i].S = (q[i - 1].S * P + t[i] - 'a' + 1);

        p[i].F = (p[i - 1].F * P) % mod;
        p[i].S = (p[i - 1].S * P);
    }
    int pal = 0;
    for (int i = 1; i <= n; i++) {
        ll l = 1, r = min(i, n - i + 1), mx = 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (ipal(i - mid + 1, i + mid - 1, i - mid + 1, i + mid - 1)) {
                l = mid + 1;
                mx = mid;
            } else r = mid - 1;
        }
        pal += mx;
        if (mx > 1) {
        sc[i - mx + 1]++;
        sc[i]--;
        us[i] -= (mx * (mx - 1)) / 2;
        cs[i]--;
        cs[i + mx - 1]++;
        uc[i] -= (mx * (mx - 1)) / 2;
        for (int j = i - mx + 1, c = 1; j < i; j++, c++) {
            tmp[j] += c;
        }
        for (int j = i + mx - 1, c = 1; j > i; j--, c++) {
            tmp[j] += c;
        }
        }
        if (i - mx > 0 && i + mx <= n) {
            auto [L, R] = mp(i - mx, i + mx);
            l = 2, r = min(L, n - R + 1);
            mx = 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (ipal(L - mid + 1, L - 1, R + 1, R + mid - 1)) {
                    l = mid + 1;
                    mx = mid;
                } else r = mid - 1;
            }
            ch[L][s[R] - 'a' + 1] += mx;
            ch[R][s[L] - 'a' + 1] += mx;
        }

        l = 1, r = min(i, n - i), mx = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (ipal(i - mid + 1, i + mid, i - mid + 1, i + mid)) {
                l = mid + 1;
                mx = mid;
            } else r = mid - 1;
        }
        if (mx > 0) {
            pal += mx;
            sc[i - mx + 1]++;
            sc[i + 1]--;
            us[i + 1] -= ((mx + 1) * mx) / 2;
            cs[i]--;
            cs[i + mx]++;
            uc[i] -= ((mx + 1) * mx) / 2;
            for (int j = i - mx + 1, c = 1; j <= i; j++, c++) tmp[j] += c;
            for (int j = i + mx, c = 1; j > i; j--, c++) tmp[j] += c;
        }
        if (i - mx > 0 && i + mx + 1 <= n) {
                auto [L, R] = mp(i - mx, i + mx + 1);
                l = 2, r = min(L, n - R + 1);
                mx = 1;
                while(l <= r) {
                    int mid = (l + r) / 2;
                    if (ipal(L - mid + 1, L - 1, R + 1, R + mid - 1)) {
                        l = mid + 1;
                        mx = mid;
                    } else r = mid - 1;
                }
                ch[L][s[R] - 'a' + 1] += mx;
                ch[R][s[L] - 'a' + 1] += mx;
            }
    }
    sc[n + 1] = cs[n + 1] = 0;
    for (int i = 2; i <= n; i++) {
        sc[i] += sc[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        sc[i] += sc[i - 1] + us[i];
    }
    for (int i = n; i > 0; --i) {
        cs[i] += cs[i + 1];
    }
    for (int i = n; i > 0; --i) {
        cs[i] += cs[i + 1] + uc[i];
    }
    ll ans = pal;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 26; j++) {
            if (j == s[i] - 'a' + 1) continue;
            ans = max(ans, pal - tmp[i] + ch[i][j]);
        }
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) solve();
    return 0;
}

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