#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000009
#define BASE 10016
struct poly_hash
{
vector<uint64_t> p, h;
poly_hash(string const &s)
{
h = vector<uint64_t>(s.size());
p = vector<uint64_t>(s.size());
h[0] = s[0];
p[0] = 1;
for (size_t i = 1; i < s.size(); i++)
{
h[i] = ((h[i - 1] * BASE) + s[i]) % MOD;
p[i] = (p[i - 1] * BASE) % MOD;
}
}
uint64_t range_hash(size_t i, size_t j)
{
if (!i)
return h[j - 1];
return (h[j - 1] - (p[j - i] * h[i - 1]) % MOD + MOD) % MOD;
}
};
struct event
{
size_t i, val, i0;
bool start;
bool operator<(event const &y) const
{
return i < y.i;
}
};
int main()
{
string s;
cin >> s;
size_t const n = s.size();
poly_hash h(s);
reverse(s.begin(), s.end());
poly_hash revh(s);
reverse(s.begin(), s.end());
size_t max_palindromes = 0;
vector<vector<int>> delta(n, vector<int>(26, 0));
vector<event> events, revevents;
for (size_t i = 0; i < n; i++)
{
size_t a = 0, b = min(i, n - i - 1);
while (a < b)
{
size_t mid = (a + b + 1) / 2;
if (h.range_hash(i - mid, i + 1) == revh.range_hash(n - 1 - (i + mid), n - i))
a = mid;
else
b = mid - 1;
}
max_palindromes += a + 1;
events.push_back({i - a, a, i - a, 1});
events.push_back({i, a, i - a, 0});
revevents.push_back({i + a, a, i + a, 1});
revevents.push_back({i, a, i + a, 0});
if (i)
{
size_t a = 0, b = min(i, n - i);
while (a < b)
{
size_t mid = (a + b + 1) / 2;
if (h.range_hash(i - mid, i) == revh.range_hash(n - 1 - (i + mid - 1), n - i))
a = mid;
else
b = mid - 1;
}
max_palindromes += a;
events.push_back({i - a, a, i - a, 1});
events.push_back({i, a, i - a, 0});
revevents.push_back({i + a - 1, a, i + a - a, 1});
revevents.push_back({i - 1, a, i + a - 1, 0});
if (a < i && i + a < n)
{
size_t oa = a;
a++;
b = min(i, n - i);
while (a < b)
{
size_t mid = (a + b + 1) / 2;
if (h.range_hash(i - mid, i - oa - 1) == revh.range_hash(n - 1 - (i + mid - 1), n - 1 - (i + oa)))
a = mid;
else
b = mid - 1;
}
delta[i - oa - 1][s[i + oa] - 'a'] += a - oa;
delta[i + oa][s[i - oa - 1] - 'a'] += a - oa;
}
}
if (i && i < n - 1 && a < i && i + a < n - 1)
{
size_t oa = a;
a++;
b = min(i, n - i - 1);
while (a < b)
{
size_t mid = (a + b + 1) / 2;
if (h.range_hash(i - mid, i - oa - 1) == revh.range_hash(n - 1 - (i + mid), n - 1 - (i + oa + 1)))
a = mid;
else
b = mid - 1;
}
delta[i - oa - 1][s[i + oa + 1] - 'a'] += a - oa;
delta[i + oa + 1][s[i - oa - 1] - 'a'] += a - oa;
}
}
sort(events.begin(), events.end());
sort(revevents.begin(), revevents.end());
size_t v = 0, c = 0;
for (auto it = events.begin(); it != events.end(); it++)
{
for (auto jt = it; jt != events.end() && jt->i == it->i; jt++)
if (jt->start)
{
c++;
}
else
{
c--;
v -= jt->val;
}
v += c;
for (size_t i = 0; i < 26; i++)
if (i != s[it->i] - 'a')
delta[it->i][i] -= v;
while (it != events.end() - 1 && (it + 1)->i == it->i)
it++;
}
v = 0, c = 0;
for (auto it = revevents.rbegin(); it != revevents.rend(); it++)
{
for (auto jt = it; jt != revevents.rend() && jt->i == it->i; jt++)
if (jt->start)
{
c++;
}
else
{
c--;
v -= jt->val;
}
v += c;
for (size_t i = 0; i < 26; i++)
if (i != s[it->i] - 'a')
delta[it->i][i] -= v;
while (it != revevents.rend() - 1 && (it + 1)->i == it->i)
it++;
}
int max_del = 0;
for (size_t i = 0; i < n; i++)
for (size_t j = 0; j < 26; j++)
max_del = max(max_del, delta[i][j]);
cout << max_palindromes + max_del << '\n';
}
Compilation message
palinilap.cpp: In function 'int main()':
palinilap.cpp:150:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
150 | if (i != s[it->i] - 'a')
| ~~^~~~~~~~~~~~~~~~~
palinilap.cpp:173:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
173 | if (i != s[it->i] - 'a')
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2888 KB |
Output is correct |
| 2 |
Correct |
7 ms |
2888 KB |
Output is correct |
| 3 |
Correct |
10 ms |
2888 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1744 KB |
Output is correct |
| 5 |
Correct |
7 ms |
2760 KB |
Output is correct |
| 6 |
Correct |
7 ms |
2888 KB |
Output is correct |
| 7 |
Correct |
7 ms |
2888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
42016 KB |
Output is correct |
| 2 |
Incorrect |
126 ms |
42120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
