#include <bits/stdc++.h>
using namespace std;
typedef long long llint;
const int maxn = 2e5+10;
const llint base = 9973;
const llint mod = 1e9+9;
int n;
char niz[maxn];
llint phas[maxn], shas[maxn];
llint pot[maxn];
llint chn[maxn][500];
llint pre[maxn], los[maxn];
llint pget(int x, int y) {
y++;
return (phas[y] - (phas[x] * pot[y - x]) % mod + mod) % mod;
}
llint sget(int x, int y) {
y++;
return (shas[x] - (shas[y] * pot[y - x]) % mod + mod) % mod;
}
int main() {
scanf("%s", niz); n = strlen(niz);
pot[0] = 1;
for (int i = 1; i <= n; i++) pot[i] = pot[i - 1] * base, pot[i] %= mod;
for (int i = 0; i < n; i++)
phas[i + 1] = (phas[i] * base) % mod + niz[i], phas[i + 1] %= mod;
for (int i = n; i > 0; i--)
shas[i - 1] = (shas[i] * base) % mod + niz[i - 1], shas[i - 1] %= mod;
llint sol = 0;
for (int i = 0; i < n; i++) {
int lo = 0;
int hi = n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
int l = i - mid;
int r = i + mid;
//printf("mid: %d\n", mid);
if (l < 0 || r >= n) hi = mid - 1;
else if (pget(l, r) == sget(l, r)) lo = mid;
else hi = mid - 1;
}
sol += lo + 1;
int l = i - lo;
int r = i + lo;
int clo = lo;
if (!(l == 0 || r == n - 1)) {
char dx = niz[l - 1], dy = niz[r + 1];
lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
int dl = l - mid - 1;
int dr = r + mid + 1;
if (dl < 0 || dr >= n) hi = mid - 1;
else if (pget(dl, l - 2) == sget(r + 2, dr)) lo = mid;
else hi = mid - 1;
}
chn[l - 1][dy] += lo + 1;
chn[r + 1][dx] += lo + 1;
}
lo = clo;
if (lo == 0) continue;
pre[l]++;
pre[i] -= lo + 1;
pre[i + 1] += 2 * lo;
pre[i + 2] -= lo + 1;
pre[r + 2]++;
}
for (int i = 1; i < n; i++) {
if (niz[i - 1] != niz[i]) continue;
int lo = 0;
int hi = n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
int l = i - mid - 1;
int r = i + mid;
if (l < 0 || r >= n) hi = mid - 1;
else if (pget(l, r) == sget(l, r)) lo = mid;
else hi = mid - 1;
}
sol += lo + 1;
int l = i - 1 - lo;
int r = i + lo;
pre[l]++;
pre[i]--;
pre[i + 1]--;
pre[r + 2]++;
if (l == 0 || r == n - 1) continue;
char dx = niz[l - 1], dy = niz[r + 1];
lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
int dl = l - mid - 1;
int dr = r + mid + 1;
if (dl < 0 || dr >= n) hi = mid - 1;
else if (pget(dl, l - 2) == sget(r + 2, dr)) lo = mid;
else hi = mid - 1;
}
chn[l - 1][dy] += lo + 1;
chn[r + 1][dx] += lo + 1;
}
for (int i = 1; i < n; i++) {
if (niz[i - 1] == niz[i]) continue;
int lo = 0;
int hi = n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
int l = i - 1 - mid;
int r = i + mid;
if (l < 0 || r >= n) hi = mid - 1;
else if (pget(l, i - 2) == sget(i + 1, r)) lo = mid;
else hi = mid - 1;
}
//printf("debug: %d %d\n", i, lo);
chn[i - 1][niz[i]] += lo + 1;
chn[i][niz[i - 1]] += lo + 1;
}
for (int i = 1; i < n; i++) pre[i] += pre[i - 1];
los[0] = pre[0];
for (int i = 1; i < n; i++) los[i] = los[i - 1] + pre[i];
//printf("los: ");
//for (int i = 0; i < n; i++) printf("%lld ", los[i]);
//printf("\n");
/**
printf("chn:\n");
for (int i = 'a'; i < 'd'; i++) {
for (int j = 0; j < n; j++) {
printf("%lld ", chn[j][i]);
}
printf("\n");
}
**/
llint bes = 0;
for (int i = 0; i < n; i++) {
for (char j = 'a'; j <= 'z'; j++) {
if (j != niz[i])
bes = max(bes, chn[i][j] - los[i]);
}
}
printf("%lld\n", sol + bes);
return 0;
}
Compilation message
palinilap.cpp: In function 'int main()':
palinilap.cpp:70:26: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[l - 1][dy] += lo + 1;
^
palinilap.cpp:71:26: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[r + 1][dx] += lo + 1;
^
palinilap.cpp:121:22: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[l - 1][dy] += lo + 1;
^
palinilap.cpp:122:22: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[r + 1][dx] += lo + 1;
^
palinilap.cpp:140:26: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[i - 1][niz[i]] += lo + 1;
^
palinilap.cpp:141:26: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[i][niz[i - 1]] += lo + 1;
^
palinilap.cpp:166:40: warning: array subscript has type 'char' [-Wchar-subscripts]
bes = max(bes, chn[i][j] - los[i]);
^
palinilap.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", niz); n = strlen(niz);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
640 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Correct |
1 ms |
768 KB |
Output is correct |
| 4 |
Correct |
1 ms |
768 KB |
Output is correct |
| 5 |
Correct |
1 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20096 KB |
Output is correct |
| 2 |
Correct |
12 ms |
20096 KB |
Output is correct |
| 3 |
Correct |
13 ms |
20096 KB |
Output is correct |
| 4 |
Correct |
9 ms |
12288 KB |
Output is correct |
| 5 |
Correct |
10 ms |
16896 KB |
Output is correct |
| 6 |
Correct |
12 ms |
20096 KB |
Output is correct |
| 7 |
Correct |
12 ms |
20096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
258 ms |
395768 KB |
Output is correct |
| 2 |
Correct |
230 ms |
395896 KB |
Output is correct |
| 3 |
Correct |
230 ms |
395768 KB |
Output is correct |
| 4 |
Correct |
241 ms |
395768 KB |
Output is correct |
| 5 |
Correct |
270 ms |
396000 KB |
Output is correct |
| 6 |
Correct |
244 ms |
395768 KB |
Output is correct |
| 7 |
Correct |
244 ms |
395768 KB |
Output is correct |
| 8 |
Correct |
93 ms |
5240 KB |
Output is correct |
| 9 |
Correct |
243 ms |
395768 KB |
Output is correct |
| 10 |
Correct |
234 ms |
395768 KB |
Output is correct |
| 11 |
Correct |
216 ms |
395728 KB |
Output is correct |
| 12 |
Correct |
245 ms |
395768 KB |
Output is correct |
| 13 |
Correct |
249 ms |
395896 KB |
Output is correct |
| 14 |
Correct |
243 ms |
395768 KB |
Output is correct |
| 15 |
Correct |
243 ms |
395768 KB |
Output is correct |
| 16 |
Correct |
232 ms |
396028 KB |
Output is correct |
| 17 |
Correct |
234 ms |
395768 KB |
Output is correct |
| 18 |
Correct |
237 ms |
395768 KB |
Output is correct |
| 19 |
Correct |
242 ms |
395896 KB |
Output is correct |
