#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
const ll NMAX = 200005;
const ll VMAX = 21;
const ll INF = 2e9;
const ll MOD = 1000000009;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;
char s[NMAX];
string ii;
ll hashes[NMAX], n, cnt;
ll hashesd[NMAX];
ll punctaj[NMAX][29];
ll palindroame[NMAX];
ll lgput(ll n, ll p) {
ll r = 1;
while(p) {
if(p & 1) {
r *= n;
r %= MOD;
}
n *= n;
n %= MOD;
p /= 2;
}
return r;
}
ll invmod(ll x) {
return lgput(x, MOD - 2);
}
ll gethash(ll i, ll j) {
if(i > j)
swap(i, j);
return ((hashes[j] - (hashes[i - 1] * lgput(base, (j - i + 1))) % MOD + MOD) % MOD); /// poate i - 2
}
ll gethashdr(ll i, ll j) {
if(i < j)
swap(i, j);
return (hashesd[j] - (hashesd[i + 1] * lgput(base, (i - j + 1))) % MOD + MOD) % MOD; /// poate i - 2
}
int main() {
ll i;
cin >> ii;
n = ii.size();
for(i = 1; i <= n * 2 - 1; i++) {
if(i % 2) {
s[i] = ii[i / 2];
} else {
s[i] = 'z' + 1;
}
}
n = n * 2 - 1;
for(i = 1; i <= n; i++) {
hashes[i] = (hashes[i - 1] * base) % MOD + (s[i] - 'a' + 1);
hashes[i] %= MOD;
}
for(i = n; i >= 1; i--) {
hashesd[i] = (hashesd[i + 1] * base) % MOD + (s[i] - 'a' + 1);
hashesd[i] %= MOD;
}
for(i = 1; i <= n; i++) {
ll r = 0, pas = (1 << nr_of_bits);
while(pas) {
ll nou = r + pas;
if(i - nou >= 1 && i + nou <= n && gethash(i - nou, i) == gethashdr(i, i + nou))
r = nou;
pas /= 2;
}
ll st = i - r;
ll dr = i + r;
cnt++;
cnt += (i - st + (s[i] == '{')) / 2;
st--;
dr++;
palindroame[st + 1]++;
palindroame[dr]--;
if(st == 0)
continue;
if(dr == n + 1)
continue;
r = 0, pas = (1 << nr_of_bits);
while(pas) {
ll nst = st - (r + pas);
ll ndr = dr + (r + pas);
if(nst >= 1 && ndr <= n && gethash(nst, st - 1) == gethashdr(dr + 1, ndr))
r += pas;
pas /= 2;
}
ll ns = st - r;
ll nd = dr + r;
punctaj[st][s[dr] - 'a'] += (st - ns + 1 + (s[i] != '{')) / 2;
punctaj[dr][s[st] - 'a'] += (nd - dr + 1 + (s[i] != '{')) / 2;
}
ll best = 0;
for(i = 1; i <= n; i++) {
palindroame[i] += palindroame[i - 1];
if(i % 2 == 0)
continue;
ll maxim = 0;
for(ll j = 0; j < 26; j++) {
maxim = max(maxim, punctaj[i][j]);
}
best = max(best, 1LL * (maxim - palindroame[i] + 1)); /// + 1 fiindca el tot ramane palindrom
}
cout << cnt + best - n / 2;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
2848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
471 ms |
50728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
