#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;
int add (int a, int b) { return a + b - (a + b < MOD ? 0 : MOD); }
int sub (int a, int b) { return a - b + (a - b >= 0 ? 0 : MOD); }
int mul (int a, int b) { return 1LL * a * b % MOD; }
ll change[mn][26], basePow[mn], n;
vector<pii> open[mn], close[mn];
struct BIT {
vector<int> tr;
BIT (int sz) : tr(sz + 1) {}
int p (int k) { return k & -k; }
void update (int k, int delta) {
if (delta < 0) delta += MOD;
for (int t = 0; k < tr.size(); t += p(k), k += p(k))
tr[k] = add(tr[k], mul(delta, basePow[t]));
}
int preSum (int k) {
int ans = 0;
for (int t = 0; k; t += p(k), k -= p(k))
ans = add(ans, mul(tr[k], basePow[t]));
return ans;
}
int query (int l, int r) {
return sub(preSum(r), mul(preSum(l - 1), basePow[r - l + 1]));
}
} 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;
if (l == r) return 1;
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 = 0;
for (int msk = 1 << 15; msk > 0; msk >>= 1)
if (checkOdd(i, wingOdd | msk)) wingOdd |= msk;
return wingOdd;
}
int calcEven (int i) {
int wingEven = 0;
for (int msk = 1 << 15; msk > 0; msk >>= 1)
if (checkEven(i, wingEven | msk)) wingEven |= msk;
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
palinilap.cpp: In member function 'void BIT::update(int, int)':
palinilap.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int t = 0; k < tr.size(); t += p(k), k += p(k))
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
7504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
7504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
7504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
10064 KB |
Output is correct |
| 2 |
Correct |
15 ms |
10248 KB |
Output is correct |
| 3 |
Correct |
21 ms |
9808 KB |
Output is correct |
| 4 |
Correct |
13 ms |
7696 KB |
Output is correct |
| 5 |
Correct |
18 ms |
9808 KB |
Output is correct |
| 6 |
Correct |
22 ms |
9732 KB |
Output is correct |
| 7 |
Correct |
23 ms |
9552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
673 ms |
33916 KB |
Output is correct |
| 2 |
Correct |
465 ms |
38928 KB |
Output is correct |
| 3 |
Correct |
392 ms |
38744 KB |
Output is correct |
| 4 |
Correct |
683 ms |
32272 KB |
Output is correct |
| 5 |
Correct |
685 ms |
32324 KB |
Output is correct |
| 6 |
Correct |
703 ms |
32292 KB |
Output is correct |
| 7 |
Correct |
706 ms |
32328 KB |
Output is correct |
| 8 |
Correct |
200 ms |
19384 KB |
Output is correct |
| 9 |
Correct |
707 ms |
32336 KB |
Output is correct |
| 10 |
Correct |
723 ms |
32428 KB |
Output is correct |
| 11 |
Correct |
466 ms |
38840 KB |
Output is correct |
| 12 |
Correct |
709 ms |
39252 KB |
Output is correct |
| 13 |
Correct |
703 ms |
33292 KB |
Output is correct |
| 14 |
Correct |
698 ms |
31500 KB |
Output is correct |
| 15 |
Correct |
692 ms |
31948 KB |
Output is correct |
| 16 |
Correct |
492 ms |
38876 KB |
Output is correct |
| 17 |
Correct |
664 ms |
28228 KB |
Output is correct |
| 18 |
Correct |
669 ms |
32580 KB |
Output is correct |
| 19 |
Correct |
657 ms |
27988 KB |
Output is correct |
