Submission #1106397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106397		_callmelucian	Palinilap (COI16_palinilap)	C++14	54 / 100	1036 ms	27820 KiB

palinilap

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll base = 21121;

ll change[mn][26], basePow[mn], n;
vector<pii> open[mn], close[mn];

struct BIT {
    vector<ll> tr;
    BIT (int sz) : tr(sz + 1) {}

    int p (int k) { return k & -k; }

    void update (int k, ll delta) {
        for (int t = 0; k < tr.size(); t += p(k), k += p(k)) {
            ll contrib = delta * basePow[t] % MOD;
            tr[k] = (tr[k] + contrib) % MOD;
        }
    }

    ll preSum (int k) {
        ll ans = 0;
        for (int t = 0; k; t += p(k), k -= p(k)) {
            ll contrib = tr[k] * basePow[t] % MOD;
            ans = (ans + contrib) % MOD;
        }
        return ans;
    }

    ll query (int l, int r) {
        return (preSum(r) - preSum(l - 1) * basePow[r - l + 1] + MOD * MOD) % MOD;
    }
} preHash(mn), sfxHash(mn);

int rev (int i) { return n - i + 1; }

bool valid (int l, int r) {
    if (l < 1 || r > n) return 0;
    //cout << "checking " << l << ".." << r << " " << preHash.query(l, r) << " " << sfxHash.query(rev(r), rev(l)) << "\n";
    return preHash.query(l, r) == sfxHash.query(rev(r), rev(l));
}

bool checkOdd (int core, int wing) {
    return valid(core - wing + 1, core + wing - 1);
}

bool checkEven (int core, int wing) {
    return valid(core - wing + 1, core + wing);
}

int calcOdd (int i) {
    int wingOdd = 1;
    for (int step = n / 2; step >= 1; step /= 2)
        while (checkOdd(i, wingOdd + step)) wingOdd += step;
    return wingOdd;
}

int calcEven (int i) {
    int wingEven = 0;
    for (int step = n / 2; step >= 1; step /= 2)
        while (checkEven(i, wingEven + step)) wingEven += step;
    return wingEven;
}

void update (int i, int c) {
    preHash.update(i, c);
    sfxHash.update(rev(i), c);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    basePow[0] = 1;
    for (int i = 1; i < mn; i++)
        basePow[i] = basePow[i - 1] * base % MOD;

    string s; cin >> s;
    n = s.length(), s = " " + s;

    for (int i = 1; i <= n; i++) update(i, s[i]);

    ll curAns = 0;
    for (int i = 1; i <= n; i++) {
        int wingOdd = calcOdd(i), wingEven = calcEven(i);
        curAns += wingOdd + wingEven;

        //cout << "dbg " << i << " " << wingOdd << " " << wingEven << "\n";

        if (1 <= i - wingOdd && i + wingOdd <= n) {
            ll delta = s[i + wingOdd] - s[i - wingOdd];

            // change s[i - wing] to s[i + wing]
            update(i - wingOdd, delta);
            change[i - wingOdd][s[i + wingOdd] - 'a'] += calcOdd(i) - wingOdd;
            update(i - wingOdd, -delta);

            // change s[i + wing] to [i - wing]
            update(i + wingOdd, -delta);
            change[i + wingOdd][s[i - wingOdd] - 'a'] += calcOdd(i) - wingOdd;
            update(i + wingOdd, delta);
        }
        if (1 <= i - wingEven && i + wingEven + 1 <= n) {
            ll delta = s[i + wingEven + 1] - s[i - wingEven];

            // change s[i - wing] to s[i + wing + 1]
            update(i - wingEven, delta);
            change[i - wingEven][s[i + wingEven + 1] - 'a'] += calcEven(i) - wingEven;
            update(i - wingEven, -delta);

            // change s[i + wing + 1] to s[i - wing]
            update(i + wingEven + 1, -delta);
            change[i + wingEven + 1][s[i - wingEven] - 'a'] += calcEven(i) - wingEven;
            update(i + wingEven + 1, delta);
        }

        if (wingOdd > 1) {
            // disturb odd palindrome
            open[i - wingOdd + 1].emplace_back(i - wingOdd, 1), close[i - 1].emplace_back(i - wingOdd, 1);
            open[i + 1].emplace_back(i + wingOdd, 0), close[i + wingOdd - 1].emplace_back(i + wingOdd, 0);
        }
        if (wingEven > 0) {
            // disturb even palindrome
            open[i - wingEven + 1].emplace_back(i - wingEven, 1), close[i].emplace_back(i - wingEven, 1);
            open[i + 1].emplace_back(i + wingEven + 1, 0), close[i + wingEven].emplace_back(i + wingEven + 1, 0);
        }
    }

    // try changing each letter
    ll ans = curAns, sumLeft = 0, cntLeft = 0, sumRight = 0, cntRight = 0;
    for (int i = 1; i <= n; i++) {
        for (pii item : open[i]) {
            int p, type; tie(p, type) = item;
            if (type) sumLeft += p, cntLeft++;
            else sumRight += p, cntRight++;
        }

        ll rem = i * cntLeft - sumLeft + sumRight - i * cntRight;
        for (int j = 0; j < 26; j++)
            if (j != s[i] - 'a') ans = max(ans, curAns - rem + change[i][j]);

        for (pii item : close[i]) {
            int p, type; tie(p, type) = item;
            if (type) sumLeft -= p, cntLeft--;
            else sumRight -= p, cntRight--;
        }
    }
    cout << ans;

    return 0;
}

Compilation message (stderr)

palinilap.cpp: In member function 'void BIT::update(int, ll)':
palinilap.cpp:27:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int t = 0; k < tr.size(); t += p(k), k += p(k)) {
      |                         ~~^~~~~~~~~~~

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