#include <bits/stdc++.h>
using namespace std;
typedef long long llint;
const int maxn = 1e5+10;
const int base = 31337;
int n;
char niz[maxn];
int phas[maxn], shas[maxn];
llint pot[maxn];
llint chn[maxn][300];
llint pre[maxn], los[maxn];
int pget(int x, int y) {
y++;
return phas[y] - phas[x] * pot[y - x];
}
int sget(int x, int y) {
y++;
return shas[x] - shas[y] * pot[y - x];
}
int main() {
scanf("%s", niz); n = strlen(niz);
pot[0] = 1;
for (int i = 1; i <= n; i++) pot[i] = pot[i - 1] * base;
for (int i = 0; i < n; i++)
phas[i + 1] = phas[i] * base + niz[i];
for (int i = n; i > 0; i--)
shas[i - 1] = shas[i] * base + niz[i - 1];
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:69:26: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[l - 1][dy] += lo + 1;
^
palinilap.cpp:70:26: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[r + 1][dx] += lo + 1;
^
palinilap.cpp:120:22: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[l - 1][dy] += lo + 1;
^
palinilap.cpp:121:22: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[r + 1][dx] += lo + 1;
^
palinilap.cpp:139:26: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[i - 1][niz[i]] += lo + 1;
^
palinilap.cpp:140:26: warning: array subscript has type 'char' [-Wchar-subscripts]
chn[i][niz[i - 1]] += lo + 1;
^
palinilap.cpp:165:40: warning: array subscript has type 'char' [-Wchar-subscripts]
bes = max(bes, chn[i][j] - los[i]);
^
palinilap.cpp:27: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 |
0 ms |
512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
640 KB |
Output is correct |
| 3 |
Correct |
1 ms |
640 KB |
Output is correct |
| 4 |
Correct |
0 ms |
640 KB |
Output is correct |
| 5 |
Correct |
0 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12288 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12288 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12288 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7552 KB |
Output is correct |
| 5 |
Correct |
6 ms |
10368 KB |
Output is correct |
| 6 |
Correct |
7 ms |
12416 KB |
Output is correct |
| 7 |
Correct |
7 ms |
12288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
238456 KB |
Output is correct |
| 2 |
Correct |
137 ms |
238584 KB |
Output is correct |
| 3 |
Correct |
129 ms |
238456 KB |
Output is correct |
| 4 |
Correct |
142 ms |
238456 KB |
Output is correct |
| 5 |
Correct |
139 ms |
238456 KB |
Output is correct |
| 6 |
Correct |
138 ms |
238456 KB |
Output is correct |
| 7 |
Correct |
139 ms |
238456 KB |
Output is correct |
| 8 |
Correct |
51 ms |
4088 KB |
Output is correct |
| 9 |
Correct |
152 ms |
238456 KB |
Output is correct |
| 10 |
Correct |
147 ms |
238516 KB |
Output is correct |
| 11 |
Correct |
140 ms |
238416 KB |
Output is correct |
| 12 |
Correct |
147 ms |
238456 KB |
Output is correct |
| 13 |
Correct |
153 ms |
238488 KB |
Output is correct |
| 14 |
Correct |
158 ms |
238456 KB |
Output is correct |
| 15 |
Correct |
165 ms |
238404 KB |
Output is correct |
| 16 |
Correct |
148 ms |
238472 KB |
Output is correct |
| 17 |
Correct |
188 ms |
238444 KB |
Output is correct |
| 18 |
Incorrect |
148 ms |
238456 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
