#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MX = 1e5 + 5;
const ll mod = 420691273;
const ll pp = 37;
string s, sr;
int n;
ll pwp[MX], ipwp[MX], hsh[MX], hshr[MX];
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;
ll hashL = hsh[cl] - (lf == 0 ? 0 : hsh[lf - 1]); if(hashL < 0) hashL += mod;
(hashL *= ipwp[lf]) %= mod;
ll hashR = hshr[cr] - (rg == 0 ? 0 : hshr[rg - 1]); if(hashR < 0) hashR += mod;
(hashR *= ipwp[rg]) %= mod;
return (hashL == hashR);
}
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] = 1;
for(int i = 1; i < MX; i ++)
pwp[i] = (pwp[i - 1] * 1ll * pp) % mod;
ipwp[MX - 1] = pw(pwp[MX - 1], mod - 2, mod);
for(int i = MX - 2; i >= 0; i --)
ipwp[i] = (ipwp[i + 1] * 1ll * pp) % mod;
for(int i = 0; i < n; i ++){
hsh[i] = (pwp[i] * 1ll * (s[i] - 'a')) % mod;
hshr[i] = (pwp[i] * 1ll * (sr[i] - 'a')) % mod;
if(i > 0){
hsh[i] += hsh[i - 1]; if(hsh[i] >= mod) hsh[i] -= mod;
hshr[i] += hshr[i - 1]; if(hshr[i] >= mod) hshr[i] -= 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 |
8 ms |
1856 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
3156 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2900 KB |
Output is correct |
| 6 |
Correct |
7 ms |
3156 KB |
Output is correct |
| 7 |
Correct |
7 ms |
3156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
28680 KB |
Output is correct |
| 2 |
Correct |
59 ms |
28680 KB |
Output is correct |
| 3 |
Correct |
62 ms |
28680 KB |
Output is correct |
| 4 |
Correct |
75 ms |
28624 KB |
Output is correct |
| 5 |
Correct |
101 ms |
28636 KB |
Output is correct |
| 6 |
Correct |
100 ms |
28632 KB |
Output is correct |
| 7 |
Correct |
86 ms |
28660 KB |
Output is correct |
| 8 |
Correct |
42 ms |
5216 KB |
Output is correct |
| 9 |
Correct |
91 ms |
28600 KB |
Output is correct |
| 10 |
Correct |
83 ms |
28600 KB |
Output is correct |
| 11 |
Correct |
61 ms |
28652 KB |
Output is correct |
| 12 |
Correct |
92 ms |
28676 KB |
Output is correct |
| 13 |
Correct |
83 ms |
28636 KB |
Output is correct |
| 14 |
Correct |
116 ms |
28632 KB |
Output is correct |
| 15 |
Correct |
108 ms |
28656 KB |
Output is correct |
| 16 |
Correct |
74 ms |
28604 KB |
Output is correct |
| 17 |
Correct |
70 ms |
28616 KB |
Output is correct |
| 18 |
Correct |
99 ms |
28616 KB |
Output is correct |
| 19 |
Correct |
71 ms |
28652 KB |
Output is correct |
