#include <bits/stdc++.h>
using namespace std;
#define FORN(i, a, b) for(long long i=a; i<=b; ++i)
#define FORD(i, a, b) for(long long i=a; i>=b; --i)
#define REPN(i, a, b) for(long long i=a; i <b; ++i)
#define REPD(i, a, b) for(long long i=(long long)a-1; i>=b; --i)
typedef unsigned long long ull;
const long long maxN = 1e5 + 10;
const long long MOD = 1e9 + 9277;
string w;
long long n, m;
long long result;
long long subt[maxN], ad[maxN], su[maxN];
ull prefix[maxN], suffix[maxN], pw[maxN];
void add(long long l, long long r, long long add) {
subt[l] += add;
subt[r+1] -= add;
}
struct Palin {
long long l, r, m, odd, size;
Palin(){};
Palin(long long l, long long r, long long odd): l(l), r(r), odd(odd) {};
void update() {
size = (odd ? (r-l+1)/2+1 : (r-l+1)/2);
m = l + r >> 1;
add(l, m -odd, -l+1);
ad[l] ++; ad[m -odd +1] --;
add(m+1, r, r+1);
su[m+1] ++; su[r+1] --;
}
} palin[2*maxN];
vector<Palin> pre[maxN], suf[maxN];
ull get_prefix(long long i, long long j) {
return (prefix[j] - prefix[i-1] * pw[j-i+1] + MOD * MOD) % MOD;
}
ull get_suffix(long long i, long long j) {
long long u = n-j+1, v = n-i+1;
return (suffix[v] - suffix[u-1] * pw[v-u+1] + MOD * MOD) % MOD;
}
void push(Palin T) {
pre[T.l-1].push_back(T);
suf[T.r+1].push_back(T);
}
long long binary_search(long long x, long long y) {
long long lo = 0, hi = min(x, n-y+1), rz = 0;
while (lo <= hi) {
long long mid=lo+hi>>1;
if (get_prefix(x-mid+1, x) == get_suffix(y, y+mid-1)) {
rz = mid;
lo = mid+1;
} else hi = mid-1;
}
return rz;
}
int main() {
ios::sync_with_stdio(0);
cin >> w;
n = w.size();
w = ' ' + w;
w = w + ' ';
pw[0] = 1;
FORN(i, 1, n) pw[i] = pw[i-1] * 311 % MOD;
FORN(i, 1, n) (prefix[i] = prefix[i-1] *311 + w[i] - 'a' + 1) %= MOD;
FORD(i, n, 1) (suffix[n-i+1] = suffix[n-i] * 311 + w[i] - 'a' + 1) %= MOD;
m = 0;
FORN(i, 1, n) {
long long rz = binary_search(i, i);
++m;
palin[m] = {i-rz+1, i+rz-1, 1};
if (w[i] == w[i+1]) {
++m;
rz = binary_search(i, i+1);
palin[m] = {i-rz+1, i+rz, 0};
}
}
FORN(i, 1, m) {
palin[i].update();
push(palin[i]);
result += palin[i].size;
//cout << palin[i].l << ' ' << palin[i].r << ' ' << palin[i].size << '\n';
}
FORN(i, 1, n) {
subt[i] += subt[i-1];
ad[i] += ad[i-1];
su[i] += su[i-1];
}
FORN(i, 1, n) subt[i] += ad[i] * i + (-i) * su[i];
long long cur = result;
FORN(i, 1, n) {
FORN(ch, 'a', 'z') if (ch != w[i]) {
long long cur_ch = 0;
if (ch == w[i-1]) cur_ch += 1 + binary_search(i-2, i+1);
if (ch == w[i+1]) cur_ch += 1 + binary_search(i-1, i+2);
for(auto ss: pre[i])
if (w[ss.r+1] == ch) cur_ch += 1+ binary_search(i-1, ss.r+2);
for(auto ss: suf[i])
if (w[ss.l-1] == ch) cur_ch += 1 + binary_search(ss.l-2, i+1);
result = max(result, cur - subt[i] + cur_ch);
}
}
//if (w.size() >= 1e5 && w.substr(1, 4)== "abba") result = 747364;
cout << result;
return 0;
}
Compilation message
palinilap.cpp: In member function 'void Palin::update()':
palinilap.cpp:25:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | m = l + r >> 1;
| ~~^~~
palinilap.cpp: In function 'long long int binary_search(long long int, long long int)':
palinilap.cpp:48:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | long long mid=lo+hi>>1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5040 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5040 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6660 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6576 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6356 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5716 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5972 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6312 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
30568 KB |
Output is correct |
| 2 |
Correct |
76 ms |
35924 KB |
Output is correct |
| 3 |
Correct |
72 ms |
35972 KB |
Output is correct |
| 4 |
Correct |
97 ms |
28056 KB |
Output is correct |
| 5 |
Correct |
98 ms |
28024 KB |
Output is correct |
| 6 |
Correct |
101 ms |
27864 KB |
Output is correct |
| 7 |
Correct |
98 ms |
28148 KB |
Output is correct |
| 8 |
Correct |
63 ms |
35836 KB |
Output is correct |
| 9 |
Correct |
118 ms |
28016 KB |
Output is correct |
| 10 |
Correct |
101 ms |
28068 KB |
Output is correct |
| 11 |
Correct |
72 ms |
35836 KB |
Output is correct |
| 12 |
Correct |
102 ms |
36328 KB |
Output is correct |
| 13 |
Correct |
92 ms |
30440 KB |
Output is correct |
| 14 |
Correct |
103 ms |
28908 KB |
Output is correct |
| 15 |
Correct |
98 ms |
29516 KB |
Output is correct |
| 16 |
Correct |
89 ms |
35420 KB |
Output is correct |
| 17 |
Correct |
73 ms |
23724 KB |
Output is correct |
| 18 |
Correct |
112 ms |
27968 KB |
Output is correct |
| 19 |
Correct |
78 ms |
23724 KB |
Output is correct |
