Submission #1106343

#TimeUsernameProblemLanguageResultExecution timeMemory
1106343_callmelucianPalinilap (COI16_palinilap)C++14
0 / 100
1059 ms32096 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 + 21; const ll base = 21121; ll basePow[mn], conOdd[mn], conEven[mn], change[mn][26]; vector<pii> open[mn], close[mn]; int n; struct BIT { vector<ll> tr; BIT (int sz) : tr(sz + 1) {} int t (int k) { return k & -k; } void update (int k, ll delta) { for (int p = 0; k < tr.size(); p += t(k), k += t(k)) { ll contrib = delta * basePow[p] % MOD; tr[k] = (tr[k] + contrib + MOD) % MOD; } } ll preSum (int k, ll ans = 0) { for (int p = 0; k; p += t(k), k -= t(k)) { ll contrib = tr[k] * basePow[p] % 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 validOdd (int c, int wing) { if (wing == 0) return 1; if (c - wing < 1 || c + wing > n) return 0; return preHash.query(c - wing, c + wing) == sfxHash.query(rev(c + wing), rev(c - wing)); } bool validEven (int c, int wing) { if (c - wing + 1 < 1 || c + wing > n) return 0; return preHash.query(c - wing + 1, c + wing) == sfxHash.query(rev(c + wing), rev(c - wing + 1)); } void update (int i, int c) { preHash.update(i, c), sfxHash.update(rev(i), c); } int calcOdd (int i) { int ans = 0; for (int step = n / 2; step >= 1; step /= 2) while (validOdd(i, ans + step)) ans += step; return ans; } int calcEven (int i) { int ans = 0; for (int step = n / 2; step >= 1; step /= 2) while (validEven(i, ans + step)) ans += step; return ans; } 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, ans = 0, rem = 0; for (int i = 1; i <= n; i++) { conOdd[i] = calcOdd(i), conEven[i] = calcEven(i); curAns += conOdd[i] + conEven[i]; int wingOdd = conOdd[i], wingEven = conEven[i]; // odd-size palindrome open[i - wingOdd].emplace_back(i, 1), open[i + 1].emplace_back(i, 1); close[i - 1].emplace_back(i, 1), close[i + wingOdd].emplace_back(i, 1); // even-size palindrome open[i - wingEven + 1].emplace_back(i, 0); close[i + wingEven].emplace_back(i, 0); if (i - wingOdd - 1 >= 1 && i + wingOdd + 1 <= n) { int delta = s[i + wingOdd + 1] - s[i - wingOdd - 1]; update(i - wingOdd - 1, delta); change[i - wingOdd - 1][s[i + wingOdd + 1] - 'a'] += calcOdd(i) - conOdd[i]; update(i - wingOdd - 1, -delta), update(i + wingOdd + 1, -delta); change[i + wingOdd + 1][s[i - wingOdd - 1] - 'a'] += calcOdd(i) - conOdd[i]; update(i + wingOdd + 1, delta); } if (i - wingEven >= 1 && i + wingEven + 1 <= n) { int delta = s[i + wingEven + 1] - s[i - wingEven]; update(i - wingEven, delta); change[i - wingEven][s[i + wingEven + 1] - 'a'] += calcEven(i) - conEven[i]; update(i - wingEven, -delta), update(i + wingEven + 1, -delta); change[i + wingEven + 1][s[i - wingEven] - 'a'] += calcEven(i) - conEven[i]; update(i + wingEven + 1, delta); } } ans = curAns; for (int i = 1; i <= n; i++) { for (pii it : open[i]) { int p, odd; tie(p, odd) = it; rem += (odd ? conOdd[p] : conEven[p]); } for (int c = 0; c < 26; c++) if (c != s[i] - 'a') ans = max(ans, curAns - rem + change[i][c]); for (pii it : close[i]) { int p, odd; tie(p, odd) = it; rem -= (odd ? conOdd[p] : conEven[p]); } } cout << ans + n; return 0; }

Compilation message (stderr)

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