#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1e9 + 7;
const int N = 2e5 + 2;
const int P = 31;
string s, t = "{";
ll n, pref[N], suff[N], p_pow[N], diff[N];
int palin[N], c_ind, c_val, st[N], en[N];
void comp_pref() {
pref[0] = suff[0] = 0;
for (int i = 1; i <= n; i++) {
pref[i] = (pref[i - 1] + ((t[i - 1] - 'a' + 1) * p_pow[i - 1] % MOD)) % MOD;
suff[i] = (suff[i - 1] + ((t[n - i] - 'a' + 1) * p_pow[i - 1] % MOD)) % MOD;
}
}
bool check_palin(int i, int len, int change) {
ll val1 = MOD + pref[i + len] - pref[i - len + 1], p1 = i - len + 1, val2 = MOD + suff[n - i + len - 1] - suff[n - i - len], p2 = n - i - len;
if (change) {
val1 = MOD + val1 + (c_val * p_pow[c_ind] % MOD);
val2 = MOD + val2 + (c_val * p_pow[n - c_ind - 1] % MOD);
}
val1 %= MOD, val2 %= MOD;
if (p1 > p2) val2 *= p_pow[p1 - p2], val2 %= MOD;
else val1 *= p_pow[p2 - p1], val1 %= MOD;
if (val1 == val2) return true;
return false;
}
void solve() {
p_pow[0] = 1;
for (int i = 1; i < N; i++) p_pow[i] = p_pow[i-1] * P % MOD;
ll ans = 0, m_val = 0, val;
cin >> s;
for (char x : s) t += x, t += '{';
n = t.length();
for (int i = 0; i <= n; i++) diff[i] = st[i] = en[i] = 0;
comp_pref();
vector<vector<int>> p_cent(n);
int l = 0, r = 0, mid;
for (int i = 0; i < n; i++) {
l = 1, r = n+1;
while (r - l > 1) {
mid = (l + r) / 2;
if (i + mid - 1 < n && i - mid + 1 >= 0 && check_palin(i, mid, 0)) {
l = mid;
} else {
r = mid;
}
}
palin[i] = l;
if (i - l >= 0 && i + l < n) p_cent[i - l].push_back(i), p_cent[i + l].push_back(i);
ans += palin[i] / 2;
}
ll cnt = 0, sum = 0;
for (int i = 0; i < n; i++) {
if (i&1) {
diff[i] = sum;
sum -= cnt;
cnt++;
sum += (palin[i] - 1) / 2;
st[i - palin[i] + 1]++, en[i + palin[i] - 1]++;
} else {
cnt++;
sum += palin[i] / 2;
st[i - palin[i] + 1]++, en[i + palin[i] - 1]++;
cnt -= en[i];
}
}
for (int i = n - 1; i >= 0; i--) {
if (i&1) {
diff[i] += sum;
sum -= cnt;
cnt++;
sum += (palin[i] - 1) / 2;
} else {
cnt++;
sum += palin[i] / 2;
cnt -= st[i];
}
}
// for (int i = 0; i < n; i++) cout << diff[i] << " ";
// cout << "\n";
for (int i = 0; i < n; i++) {
if (!(i&1)) continue;
for (char x = 'a'; x <= 'z'; x++) {
c_ind = i, c_val = x - t[i], val = 0;
for (int ind : p_cent[i]) {
l = palin[ind], r = n+1;
while (r - l > 1) {
mid = (l + r) / 2;
if (ind + mid - 1 < n && ind - mid + 1 >= 0 && check_palin(ind, mid, 1)) {
l = mid;
} else {
r = mid;
}
}
val += l / 2 - palin[ind] / 2;
// cout << ind << " " << l << " " << palin[ind] << " " << x << "\n";
}
m_val = max(m_val, val - diff[i]);
}
}
cout << ans + m_val << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
t = 1;
// cin >> t;
while(t--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1884 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2032 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1884 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
50 ms |
2648 KB |
Output is correct |
| 3 |
Correct |
96 ms |
2648 KB |
Output is correct |
| 4 |
Correct |
54 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
84 ms |
2648 KB |
Output is correct |
| 6 |
Correct |
102 ms |
2820 KB |
Output is correct |
| 7 |
Correct |
112 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1061 ms |
17696 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
