Submission #677713

#TimeUsernameProblemLanguageResultExecution timeMemory
677713finn__Palinilap (COI16_palinilap)C++17
0 / 100
140 ms53404 KiB
#include <bits/stdc++.h> using namespace std; #define MOD 1000000009 #define BASE 10016 struct poly_hash { vector<uint64_t> p, h; poly_hash(string const &s) { h = vector<uint64_t>(s.size()); p = vector<uint64_t>(s.size()); h[0] = s[0]; p[0] = 1; for (size_t i = 1; i < s.size(); i++) { h[i] = ((h[i - 1] * BASE) + s[i]) % MOD; p[i] = (p[i - 1] * BASE) % MOD; } } uint64_t range_hash(size_t i, size_t j) { if (!i) return h[j - 1]; return (h[j - 1] - (p[j - i] * h[i - 1]) % MOD + MOD) % MOD; } }; struct event { size_t i, val; bool start; bool operator<(event const &y) const { return i < y.i; } }; int main() { string s; cin >> s; size_t const n = s.size(); poly_hash h(s); reverse(s.begin(), s.end()); poly_hash revh(s); reverse(s.begin(), s.end()); size_t max_palindromes = 0; vector<vector<int>> delta(n, vector<int>(26, 0)); vector<event> events, revevents; for (size_t i = 0; i < n; i++) { size_t a = 0, b = i; while (a < b) { size_t mid = (a + b + 1) / 2; if (h.range_hash(i - mid, i + 1) == revh.range_hash(n - 1 - (i + mid), n - i)) a = mid; else b = mid - 1; } max_palindromes += a + 1; if (i) { size_t a = 0, b = i; while (a < b) { size_t mid = (a + b + 1) / 2; if (h.range_hash(i - mid, i) == revh.range_hash(n - 1 - (i + mid - 1), n - i)) a = mid; else b = mid - 1; } max_palindromes += a; if (i < n - 1 && a < i && i + 1 < n - 1) { size_t oa = a; a++; b = i; while (a < b) { size_t mid = (a + b + 1) / 2; if (h.range_hash(i - mid, i - oa - 1) == revh.range_hash(n - 1 - (i + mid - 1), n - 1 - (i + oa))) a = mid; else b = mid - 1; } delta[i - oa - 1][s[i + oa] - 'a'] += a - oa; delta[i + oa][s[i - oa - 1] - 'a'] += a - oa; events.push_back({i - oa, 0, 1}); events.push_back({i, oa, 0}); revevents.push_back({i + oa - 1, 0, 1}); revevents.push_back({i - 1, oa, 0}); } } if (i && i < n - 1 && a < i && i + a < n - 1) { size_t oa = a; a++; b = i; while (a < b) { size_t mid = (a + b + 1) / 2; if (h.range_hash(i - mid, i - oa - 1) == revh.range_hash(n - 1 - (i + mid), n - 1 - (i + oa + 1))) a = mid; else b = mid - 1; } delta[i - oa - 1][s[i + oa + 1] - 'a'] += a - oa; delta[i + oa + 1][s[i - oa - 1] - 'a'] += a - oa; events.push_back({i - oa, 0, 1}); events.push_back({i, oa, 0}); revevents.push_back({i + oa, 0, 1}); revevents.push_back({i, oa, 0}); } } sort(events.begin(), events.end()); sort(revevents.begin(), revevents.end()); size_t v = 0, c = 0; for (auto it = events.begin(); it != events.end(); it++) { for (auto jt = it; jt != events.end() && jt->i == it->i; jt++) if (jt->start) { c++; } else { c--; v -= jt->val; } v += c; for (size_t i = 0; i < 26; i++) if (i != s[it->i] - 'a') delta[it->i][i] -= v; while (it != events.end() - 1 && (it + 1)->i == it->i) it++; } v = 0, c = 0; for (auto it = revevents.rbegin(); it != revevents.rend(); it++) { for (auto jt = it; jt != revevents.rend() && jt->i == it->i; jt++) if (jt->start) { c++; } else { c--; v -= jt->val; } v += c; for (size_t i = 0; i < 26; i++) if (i != s[it->i] - 'a') delta[it->i][i] -= v; while (it != revevents.rend() - 1 && (it + 1)->i == it->i) it++; } int max_del = 0; for (size_t i = 0; i < n; i++) for (size_t j = 0; j < 26; j++) max_del = max(max_del, delta[i][j]); cout << max_palindromes + max_del << '\n'; }

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:148:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  148 |             if (i != s[it->i] - 'a')
      |                 ~~^~~~~~~~~~~~~~~~~
palinilap.cpp:171:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  171 |             if (i != s[it->i] - 'a')
      |                 ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...