#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int M=1e9+696969;
const ar<int, 2> B={283, 9128};
ar<int, 2> operator+ (ar<int, 2> a, ar<int, 2> b) {
for (int i = 0; i < 2; ++i)
if ((a[i] += b[i]) >= M)
a[i] -= M;
return a;
}
ar<int, 2> operator- (ar<int, 2> a, ar<int, 2> b) {
for (int i = 0; i < 2; ++i)
if ((a[i] -= b[i]) < 0)
a[i] += M;
return a;
}
ar<int, 2> operator* (ar<int, 2> a, ar<int, 2> b) {
for (int i = 0; i < 2; ++i)
a[i] = (ll)a[i] * b[i] % M;
return a;
}
ar<int, 2> mk(char c) {
return {c, c};
}
const int mxN=1e5;
int n, d1[mxN], d2[mxN], change[26][mxN];
string s;
ar<int, 2> p[mxN], h1[mxN+1], h2[mxN+1];
ll bad[mxN], pref[mxN];
vector<ar<int, 2>> cands[mxN][26];
ar<int, 2> get1(int l, int r, ar<int, 2> change={}) {
return h1[r+1]-h1[l]*p[r-l+1]+change;
}
ar<int, 2> get2(int l, int r, ar<int, 2> change={}) {
return h2[l]-h2[r+1]*p[r-l+1]+change;
}
bool ck(int l, int r, int i=-1, ar<int, 2> change={}) {
assert(0<=l&&l<=r&&r<n);
if (i<l||i>r)
return get1(l, r)==get2(l, r);
return get1(l, r)+change*p[r-i]==get2(l, r)+change*p[i-l];
}
int solve1(int i, int pos=-1, ar<int, 2> change={}) { // get number of palindromes centered at s[i]
assert(0<=i&&i<n);
int lb=1, rb=min(i+1, n-i);
while(lb<rb) {
int mid=(lb+rb+1)/2;
if (ck(i-mid+1, i+mid-1, pos, change))
lb=mid;
else
rb=mid-1;
}
return lb;
}
int solve2(int i, int pos=-1, ar<int, 2> change={}) { // get number of palindromes centered at s[i]-s[i+1]
assert(0<=i&&i<n-1);
//if (s[i]!=s[i+1]&&pos==-1)
// return 0;
int lb=0, rb=min(i+1, n-1-i);
while(lb<rb) {
int mid=(lb+rb+1)/2;
if (ck(i-mid+1, i+mid, pos, change))
lb=mid;
else
rb=mid-1;
}
return lb;
}
void add_seg(int l, int r) {
assert(0<=l&&l<=r&&r<n);
++pref[l], --pref[r+1];
bad[r+1]-=r-l+1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s, n=s.size();
p[0]={1, 1};
for (int i=1; i<n; ++i)
p[i]=p[i-1]*B;
for (int i=0; i<n; ++i)
h1[i+1]=h1[i]*B+mk(s[i]);
for (int i=n-1; ~i; --i)
h2[i]=h2[i+1]*B+mk(s[i]);
ll base=0;
for (int i=0; i<n; ++i) {
d1[i]=solve1(i);
d2[i]=i+1<n?solve2(i):0;
base+=d1[i]+d2[i];
}
for (int rep=0; rep<2; ++rep) {
for (int i=0; i<n; ++i) {
if (d1[i]>1)
add_seg(i-d1[i]+1, i-1);
if (i-d1[i]+1&&i+d1[i]<n)
cands[i-d1[i]][s[i+d1[i]]-'a'].push_back({i, 1});
}
for (int i=0; i+1<n; ++i) {
if (d2[i])
add_seg(i-d2[i]+1, i);
if (i-d2[i]+1&&i+d2[i]+1<n)
cands[i-d2[i]][s[i+d2[i]+1]-'a'].push_back({i, 2});
}
for (int i=0; i<n; ++i) {
if (i) {
pref[i]+=pref[i-1];
bad[i]+=bad[i-1];
}
bad[i]+=pref[i];
for (int j=0; j<26; ++j) {
if (s[i]=='a'+j)
continue;
change[j][i]-=bad[i];
for (auto [c, t] : cands[i][j])
change[j][i]+=t==1?solve1(c, i, mk('a'+j)-mk(s[i]))-d1[c]:solve2(c, i, mk('a'+j)-mk(s[i]))-d2[c];
}
}
reverse(d1, d1+n);
reverse(d2, d2+n-1);
for (int j=0; j<26; ++j)
reverse(change[j], change[j]+n);
memset(bad, 0, sizeof(bad));
memset(pref, 0, sizeof(pref));
for (int i=0; i<n; ++i)
for (int j=0; j<26; ++j)
cands[i][j].clear();
reverse(s.begin(), s.end());
for (int i=0; i<n; ++i)
h1[i+1]=h1[i]*B+mk(s[i]);
for (int i=n-1; ~i; --i)
h2[i]=h2[i+1]*B+mk(s[i]);
}
ll ans=base;
for (int i=0; i<26; ++i)
ans=max(ans, base+*max_element(change[i], change[i]+n));
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
63060 KB |
Output is correct |
| 2 |
Correct |
31 ms |
63060 KB |
Output is correct |
| 3 |
Correct |
32 ms |
63004 KB |
Output is correct |
| 4 |
Correct |
30 ms |
63188 KB |
Output is correct |
| 5 |
Correct |
30 ms |
63108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
63928 KB |
Output is correct |
| 2 |
Correct |
38 ms |
63952 KB |
Output is correct |
| 3 |
Correct |
46 ms |
64088 KB |
Output is correct |
| 4 |
Correct |
39 ms |
63728 KB |
Output is correct |
| 5 |
Correct |
40 ms |
64024 KB |
Output is correct |
| 6 |
Correct |
44 ms |
64044 KB |
Output is correct |
| 7 |
Correct |
43 ms |
63948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
370 ms |
80020 KB |
Output is correct |
| 2 |
Incorrect |
306 ms |
81752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
