#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<
typedef long long ll;
typedef pair<int, int> point;
const ll MAXN = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll BAZA = 1307;
string s;
int h[MAXN], h_[MAXN], pot[MAXN];
void calcHash(){
pot[0] = 1;
h[0] = s[0];
FOR(i, 1, (int)s.size()){
h[i] = (h[i - 1] * BAZA + s[i]) % MOD;
pot[i] = pot[i - 1] * BAZA % MOD;
}
h_[0] = s[s.size() - 1];
for(int i = s.size() - 2, cnt = 1; i >= 0; --i, ++cnt)
h_[cnt] = (h_[cnt - 1] * BAZA + s[i]) % MOD;
}
ll calc(ll x, ll y){
ll k = 0;
if(x) k = (ll)h[x - 1] * pot[y] % MOD;
return ((((ll)h[x + y - 1] - k) % MOD) + MOD) % MOD;
}
ll calc_(ll x, ll y){
ll k = 0;
if(x) k = (ll)h_[x - 1] * pot[y] % MOD;
return ((((ll)h_[x + y - 1] - k) % MOD) + MOD) % MOD;
}
int cntDec[MAXN];
ll decrease[MAXN];
ll increase[MAXN], letInc[MAXN][30];
int main(){
ios_base::sync_with_stdio(false); cin.tie(0),
cin >> s;
calcHash();
ll sol = 0;
int len = s.size();
REP(i, len){
//neparni
ll lo = 1, hi = min(i + 1, len - i);
while(lo < hi){
ll mid = (lo + hi + 1) >> 1;
if(i + mid - 1 >= s.size() || len - i - 1 + mid - 1 >= s.size()){
assert(s.size() == 0);
}
if(calc(i, mid) == calc_(len - i - 1, mid))
lo = mid;
else
hi = mid - 1;
}
cntDec[i - lo + 1] ++;
cntDec[i + 1] -= 2;
cntDec[i + lo + 1] ++;
sol += lo;
increase[i] += lo;
ll jump = lo + 1;
lo = 0, hi = min(i + 1, len - i) - jump;
while(lo < hi){
ll mid = (lo + hi + 1) >> 1;
if(i + jump + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
assert(s.size() == 0);
}
if(calc(i + jump, mid) == calc_(len - i + jump - 1, mid))
lo = mid;
else
hi = mid - 1;
}
letInc[i + jump - 1][s[i - jump + 1] - 'a'] += lo + 1;
letInc[i - jump + 1][s[i + jump - 1] - 'a'] += lo + 1;
if(i == len - 1) continue;
//neparni
lo = 0, hi = min(i + 1, len - i - 1);
while(lo < hi){
ll mid = (lo + hi + 1) >> 1;
if(i + 1 + mid - 1 >= s.size() || len - i - 1 - mid + 1 >= s.size()){
assert(s.size() == 0);
}
if(calc(i + 1, mid) == calc_(len - i - 1, mid))
lo = mid;
else
hi = mid - 1;
}
sol += lo;
if(lo){
cntDec[i - lo + 1] ++;
cntDec[i + 1] --;
cntDec[i + 2] --;
cntDec[i + lo + 2] ++;
}
jump = lo + 1;
lo = 0, hi = min(i + 1, len - i - 1) - jump;
while(lo < hi){
ll mid = (lo + hi + 1) >> 1;
if(i + jump + 1 + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
assert(s.size() == 0);
}
if(calc(i + jump + 1, mid) == calc_(len - i + jump - 1, mid))
lo = mid;
else
hi = mid - 1;
}
letInc[i + jump][s[i - jump + 1] - 'a'] += lo + 1;
letInc[i - jump + 1][s[i + jump] - 'a'] += lo + 1;
}
ll cnt = 0, curr = 0;
REP(i, len){
cnt += cntDec[i];
curr += cnt;
decrease[i] = curr;
}
ll best = 0;
REP(i, len)
REP(j, 26){
best = max(best, increase[i] + letInc[i][j] - decrease[i]);
}
cout << sol + best;
}
Compilation message
palinilap.cpp: In function 'int main()':
palinilap.cpp:64:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + mid - 1 >= s.size() || len - i - 1 + mid - 1 >= s.size()){
~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:64:65: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + mid - 1 >= s.size() || len - i - 1 + mid - 1 >= s.size()){
~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:85:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + jump + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:85:79: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + jump + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:102:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + 1 + mid - 1 >= s.size() || len - i - 1 - mid + 1 >= s.size()){
~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:102:69: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + 1 + mid - 1 >= s.size() || len - i - 1 - mid + 1 >= s.size()){
~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:125:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + jump + 1 + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:125:83: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + jump + 1 + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
600 KB |
Output is correct |
| 3 |
Correct |
3 ms |
600 KB |
Output is correct |
| 4 |
Correct |
2 ms |
600 KB |
Output is correct |
| 5 |
Correct |
3 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1872 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1900 KB |
Output is correct |
| 3 |
Correct |
8 ms |
1900 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1900 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1900 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1900 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
27372 KB |
Output is correct |
| 2 |
Correct |
80 ms |
27404 KB |
Output is correct |
| 3 |
Correct |
100 ms |
27500 KB |
Output is correct |
| 4 |
Correct |
104 ms |
27500 KB |
Output is correct |
| 5 |
Correct |
103 ms |
27500 KB |
Output is correct |
| 6 |
Correct |
104 ms |
27500 KB |
Output is correct |
| 7 |
Runtime error |
130 ms |
54160 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
