Submission #1106400

#TimeUsernameProblemLanguageResultExecution timeMemory
1106400_callmelucianPalinilap (COI16_palinilap)C++14
54 / 100
1067 ms39784 KiB
#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]; update(i - wingOdd, delta); ll contrib = calcOdd(i) - wingOdd; change[i - wingOdd][s[i + wingOdd] - 'a'] += contrib; change[i + wingOdd][s[i - wingOdd] - 'a'] += contrib; update(i - wingOdd, -delta); } if (1 <= i - wingEven && i + wingEven + 1 <= n) { ll delta = s[i + wingEven + 1] - s[i - wingEven]; update(i - wingEven, delta); ll contrib = calcEven(i) - wingEven; change[i - wingEven][s[i + wingEven + 1] - 'a'] += contrib; change[i + wingEven + 1][s[i - wingEven] - 'a'] += contrib; update(i - wingEven, -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)) {
      |                         ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...