#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int M=1e9+696969;
const ar<int, 2> B={129, 7282};
#define dbg(x) cerr << "[" << #x << "] = [" << x << "]\n"
template<class A, size_t sz> ostream& operator<< (ostream& out, ar<A, sz> a) {
out << '[';
for (int i = 0; i < sz; ++i) {
if (i > 0) out << ", ";
out << a[i];
}
return out << ']';
}
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];
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)
cands[i-d1[i]].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)
cands[i-d2[i]].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];
ll tot=bad[i];
for (auto [c, t] : cands[i])
tot+=t==1?d1[c]:d2[c];
for (int j=0; j<26; ++j) {
if (s[i]=='a'+j)
continue;
change[j][i]-=tot;
for (auto [c, t] : cands[i]) {
change[j][i]+=t==1?solve1(c, i, mk('a'+j)-mk(s[i])):solve2(c, i, mk('a'+j)-mk(s[i]));
//if (!rep&&!i&&j==1)
// cout << c << " " << t << " " << (t==1?solve1(c, i, mk('a'+j)-mk(s[i])):solve2(c, i, mk('a'+j)-mk(s[i]))) << endl;
}
}
}
//if (!rep)
// cout << change[1][2] << endl;
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)
cands[i].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]);
}
//for (int i=0; i<3; ++i)
// for (int j=0; j<3; ++j)
// cout << i << " " << j << " " << change[j][i] << endl;
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 |
3 ms |
4308 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4308 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4352 KB |
Output is correct |
| 4 |
Correct |
4 ms |
4308 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
5128 KB |
Output is correct |
| 2 |
Correct |
96 ms |
5208 KB |
Output is correct |
| 3 |
Correct |
165 ms |
5300 KB |
Output is correct |
| 4 |
Correct |
98 ms |
4820 KB |
Output is correct |
| 5 |
Correct |
142 ms |
5116 KB |
Output is correct |
| 6 |
Correct |
164 ms |
5272 KB |
Output is correct |
| 7 |
Correct |
163 ms |
5208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
15700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
