#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 2 * 1e5 + 10, M = 26 + 10;
const ll mod = 1e9 + 7;
ll um(ll a, ll b){
return ((1LL * a * b) % mod + mod) % mod;
}
ll subr(ll a, ll b){
return ((1LL * a - b) % mod + mod) % mod;
}
ll add(ll a, ll b){
return (1LL * a + b) % mod;
}
ll p = 3371, pr[N], pr2[N];
ll arr[N][M], x[N], hs1[N], hs2[N], n;
ll get(ll l1, ll r1, ll l2, ll r2){
ll s1 = hs1[r1], s2 = subr(hs2[r2], hs2[l2 + 1]);
if(l1 != 0) s1 = subr(s1, hs1[l1 - 1]);
if(l1 >= n - l2 - 1) s2 = um(s2, pr[l1 - (n - l2 - 1)]);
else s1 = um(s1, pr[n - l2 - 1 - l1]);
if(s1 == s2) return true;
return false;
}
ll in[N], out[N], incnt[N], outcnt[N];
ll getr(ll from, ll to){
ll l = 0, r = min(n - to, from + 1);
while(r - l > 1){
ll mid = (r + l) / 2;
if(get(to, to + mid, from, from - mid)) l = mid;
else r = mid;
}
if(x[from] != x[to]) r = 0;
return r;
}
void calc(ll from, ll to){
ll r = getr(from, to);
if(from - r >= 0 && to + r < n){
from = from - r - 1;
to = to + r + 1;
if(from < 0 || to >= n){
from++;
to--;
arr[from][x[to]]++;
arr[to][x[from]]++;
return;
}
ll lx = 0, rx = min(from + 1, n - to), cm = 1;
while(rx - lx > 1){
ll mid = (rx + lx) / 2;
if(get(to, to + mid, from, from - mid)) lx = mid;
else rx = mid;
}
if(get(to, to + lx, from, from - lx) == true) cm = lx + 2;
from++;
to--;
arr[from][x[to]] += cm;
arr[to][x[from]] += cm;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin >> s;
n = (ll)s.size();
// build
pr[0] = 1LL;
for(ll i = 1; i <= n; i++){
pr[i] = um(pr[i - 1], p);
}
for(ll i = 0; i < n; i++){
x[i] = s[i] - 'a';
if(i == 0) hs1[i] = x[i];
else hs1[i] = add(hs1[i - 1], um(x[i], pr[i]));
}
for(ll i = n - 1; i >= 0; i--){
hs2[i] = add(hs2[i + 1], um(x[i], pr[n - i - 1]));
}
// take answer
for(ll i = 0; i < n; i++){
ll r = getr(i, i);
in[i] += r;
incnt[i]++;
incnt[i + r]--;
arr[i][x[i]] -= r;
out[i] += r;
outcnt[i]++;
if(i - r >= 0) outcnt[i - r]--;
r = getr(i, i + 1);
if(r == 0 || x[i] != x[i + 1]) continue;
in[i + 1] += r;
incnt[i + 1]++;
incnt[i + 1 + r]--;
out[i] += r;
outcnt[i]++;
if(i - r >= 0) outcnt[i - r]--;
}
ll cur = 0, c = 0, ans = 0;
for(ll i = 0; i < n; i++){
cur += in[i];
c += incnt[i];
arr[i][x[i]] += cur;
cur -= c;
}
cur = c = 0;
for(ll i = n - 1; i >= 0; i--){
cur += out[i];
c += outcnt[i];
arr[i][x[i]] += cur;
cur -= c;
ans += arr[i][x[i]];
}
// for(ll i = 0; i < n; i++){
// cout << arr[i][x[i]] << " ";
// }
// cout << endl;
cur = ans;
for(ll i = 0; i < n; i++){
calc(i, i);
calc(i, i + 1);
}
ll f1 = -1, f2 = -1;
for(ll i = 0; i < n; i++){
for(ll j = 0; j < 26; j++){
if(j == x[i]) continue;
if(cur + arr[i][j] - arr[i][x[i]] + 1 > ans){
ans = max(ans, cur + arr[i][j] - arr[i][x[i]] + 1);
f1 = i;
f2 = j;
}
}
}
if(f1 != -1) x[f1] = f2;
for(ll i = 0; i < n; i++){
if(i == 0) hs1[i] = x[i];
else hs1[i] = add(hs1[i - 1], um(x[i], pr[i]));
}
for(ll i = n - 1; i >= 0; i--){
hs2[i] = add(hs2[i + 1], um(x[i], pr[n - i - 1]));
}
ll real = 0;
for(ll i = 0; i < n; i++){
real += getr(i, i);
real += getr(i, i + 1);
}
cout << real;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12792 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
6 ms |
12760 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
9 ms |
12632 KB |
Output is correct |
| 7 |
Correct |
9 ms |
12636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
233 ms |
40732 KB |
Output is correct |
| 2 |
Correct |
190 ms |
40528 KB |
Output is correct |
| 3 |
Correct |
195 ms |
40528 KB |
Output is correct |
| 4 |
Correct |
230 ms |
40712 KB |
Output is correct |
| 5 |
Correct |
223 ms |
40728 KB |
Output is correct |
| 6 |
Incorrect |
222 ms |
40732 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
