#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MX = 1e5 + 5;
const ll mod = 420691273;
const ll mod2 = 1e9 + 9;
const ll pp = 37;
const ll pp2 = 31;
string s, sr;
int n;
ll pwp[MX][2], ipwp[MX][2], hsh[MX][2], hshr[MX][2];
ll pw(ll b, ll e, ll m){
ll r = 1ll; b %= m;
for(; e > 0; e /= 2, (b *= b) %= m)
if(e % 2) (r *= b) %= m;
return r;
}
bool check_palindrome(int lf, int cl, int cr, int rg){
rg = n - 1 - rg; cr = n - 1 - cr;
if(lf > cl || rg > cr || lf < 0 || rg < 0) return 0;
bool ok = 1;
for(int i = 0; i < 2; i ++){
ll hashL = hsh[cl][i] - (lf == 0 ? 0 : hsh[lf - 1][i]); if(hashL < 0) hashL += (i ? mod2 : mod);
(hashL *= ipwp[lf][i]) %= (i ? mod2 : mod);
ll hashR = hshr[cr][i] - (rg == 0 ? 0 : hshr[rg - 1][i]); if(hashR < 0) hashR += (i ? mod2 : mod);
(hashR *= ipwp[rg][i]) %= (i ? mod2 : mod);
ok &= (hashL == hashR);
}
return ok;
}
ll add[MX][30]; // change s[i] to j + 'a', how many palindromes are added
ll delRunning[MX]; ll delCap[MX];
/*
a b c d d c b a | a b c b a
1 2 3 4 4 3 2 1 | 1 2 0 2 1
changing s[i] will delete palindromes according to above
for left side, represent as i - x, x constant (delRuuning = 1, delCap = -x)
for right, represent as x - i, x constant (delRunning = -1, delCap = x)
when added, will become in the form of i * delRunning + delCap
is range update point query, with all queries processed at the end -> offline prefix difference
*/
int main(){
cin >> s;
sr = s; reverse(sr.begin(),sr.end());
n = s.size();
pwp[0][0] = 1;
for(int i = 1; i < MX; i ++)
pwp[i][0] = (pwp[i - 1][0] * 1ll * pp) % mod;
ipwp[MX - 1][0] = pw(pwp[MX - 1][0], mod - 2, mod);
for(int i = MX - 2; i >= 0; i --)
ipwp[i][0] = (ipwp[i + 1][0] * 1ll * pp) % mod;
pwp[0][1] = 1;
for(int i = 1; i < MX; i ++)
pwp[i][1] = (pwp[i - 1][1] * 1ll * pp2) % mod2;
ipwp[MX - 1][1] = pw(pwp[MX - 1][1], mod2 - 2, mod2);
for(int i = MX - 2; i >= 0; i --)
ipwp[i][1] = (ipwp[i + 1][1] * 1ll * pp2) % mod2;
for(int i = 0; i < n; i ++){
for(int j = 0; j < 2; j ++){
hsh[i][j] = (pwp[i][j] * 1ll * (s[i] - 'a')) % (j ? mod2 : mod);
hshr[i][j] = (pwp[i][j] * 1ll * (sr[i] - 'a')) % (j ? mod2 : mod);
if(i > 0){
hsh[i][j] += hsh[i - 1][j]; if(hsh[i][j] >= (j ? mod2 : mod)) hsh[i][j] -= (j ? mod2 : mod);
hshr[i][j] += hshr[i - 1][j]; if(hshr[i][j] >= (j ? mod2 : mod)) hshr[i][j] -= (j ? mod2 : mod);
}
}
}
ll base_answer = 0ll;
for(int cl = 0; cl < n; cl ++){
for(int cr = cl; cr <= cl + 1; cr ++){
int lf = 0, rg = min(cl + 1, n - cr), rs = lf;
for(int md; lf <= rg;){
md = (lf + rg + 1) / 2;
if(check_palindrome(cl - md + 1, cl, cr, cr + md - 1)){
rs = md;
lf = md + 1;
}else{
rg = md - 1;
}
}
base_answer += rs;
// process deleting
if(cl == cr){
// odd case
delRunning[cl - rs + 1] ++; delRunning[cl] --; // left side
delCap[cl - rs + 1] -= cl - rs; delCap[cl] += cl - rs;
delRunning[cr + 1] --; delRunning[cr + rs] ++; // right side
delCap[cr + 1] += cr + rs; delCap[cr + rs] -= cr + rs;
}else{
// even case
delRunning[cl - rs + 1] ++; delRunning[cl + 1] --; // left side
delCap[cl - rs + 1] -= cl - rs; delCap[cl + 1] += cl - rs;
delRunning[cr] --; delRunning[cr + rs] ++; // right side
delCap[cr] += cr + rs; delCap[cr + rs] -= cr + rs;
}
// process adding
int xl = cl - rs, xr = cr + rs; rs ++;
if(xl < 0 || xr >= n) continue;
lf = 0, rg = min(cl + 1, n - cr) - rs; rs = lf;
for(int md; lf <= rg;){
md = (lf + rg + 1) / 2;
if(check_palindrome(xl - md, xl - 1, xr + 1, xr + md)){
rs = md;
lf = md + 1;
}else{
rg = md - 1;
}
}
add[xl][s[xr] - 'a'] += rs + 1;
add[xr][s[xl] - 'a'] += rs + 1;
}
}
ll best_change = 0ll;
ll run = 0ll, cap = 0ll;
for(int i = 0; i < n; i ++){
run += delRunning[i];
cap += delCap[i];
for(int j = 0; j < 26; j ++) if(s[i] - 'a' != j){
best_change = max(best_change, add[i][j] - (run * 1ll * i + cap));
}
}
cout << base_answer + best_change << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3412 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3412 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3412 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4828 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4820 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4820 KB |
Output is correct |
| 4 |
Correct |
6 ms |
4308 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4564 KB |
Output is correct |
| 6 |
Correct |
7 ms |
4820 KB |
Output is correct |
| 7 |
Correct |
8 ms |
4820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
31724 KB |
Output is correct |
| 2 |
Correct |
87 ms |
31716 KB |
Output is correct |
| 3 |
Correct |
89 ms |
31728 KB |
Output is correct |
| 4 |
Correct |
126 ms |
31896 KB |
Output is correct |
| 5 |
Correct |
108 ms |
31692 KB |
Output is correct |
| 6 |
Correct |
109 ms |
31808 KB |
Output is correct |
| 7 |
Correct |
112 ms |
31788 KB |
Output is correct |
| 8 |
Correct |
60 ms |
8396 KB |
Output is correct |
| 9 |
Correct |
111 ms |
31804 KB |
Output is correct |
| 10 |
Correct |
115 ms |
31760 KB |
Output is correct |
| 11 |
Correct |
75 ms |
31808 KB |
Output is correct |
| 12 |
Correct |
113 ms |
31736 KB |
Output is correct |
| 13 |
Correct |
116 ms |
31708 KB |
Output is correct |
| 14 |
Correct |
107 ms |
31784 KB |
Output is correct |
| 15 |
Correct |
116 ms |
31764 KB |
Output is correct |
| 16 |
Correct |
98 ms |
31772 KB |
Output is correct |
| 17 |
Correct |
108 ms |
31916 KB |
Output is correct |
| 18 |
Correct |
116 ms |
31844 KB |
Output is correct |
| 19 |
Correct |
110 ms |
31820 KB |
Output is correct |
