#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e5+5, p=29, mod=1e9+7;
inline int sum(int a, int b){
if(a+b>=mod){
return a+b-mod;
}
else if(a+b<0){
return a+b+mod;
}
return a+b;
}
inline int mul(int a, int b){
return (ll)a*b%mod;
}
int pref[maxn], suff[maxn];
int n;
string s;
int pot[maxn];
int sw[maxn];
ll oduz[maxn];
ll dodaj[maxn][p];
ll sol;
void precompute(){
pot[0]=1;
for(int i=1; i<maxn; i++){
pot[i]=mul(pot[i-1], p);
}
}
bool provjeri(int x, int y, int kolko){
return sum(pref[x+1], -mul(pref[x-kolko], pot[kolko+1]))==sum(suff[n-y], -mul(suff[n-y-kolko-1], pot[kolko+1]));
}
int binary(int x, int y){
int lo=0, hi=min(x+1, n-y), mid;
while(lo<hi){
mid=(lo+hi)/2;
if(provjeri(x, y, mid)){
lo=mid+1;
}
else{
hi=mid;
}
}
return lo;
}
void rijesi(int x, bool p){
int l, d;
if(p){
l=x;
d=x+1;
}
else{
l=x-1;
d=x+1;
}
int val;
if(l<0 || d>=n){
val=0;
}
else{
val=binary(l, d);
}
l-=val;
d+=val;
sol+=x-l;
// cout << x << " " << p << " " << x-l << endl;
// cout << x << " " << p << " " << l << " " << d << '\n';
if(p){
sw[l+1]++;
sw[x+1]--;
sw[x+2]--;
sw[d+1]++;
}
else{
sw[l+1]++;
sw[x+1]-=2;
sw[d+1]++;
oduz[x]+=x-l;
}
}
void rijesi2(int x, bool p){
int l, d;
if(p){
l=x;
d=x+1;
}
else{
l=x-1;
d=x+1;
}
if(l<0 || d>=n){
return;
}
int val;
val=binary(l, d);
l-=val;
d+=val;
if(l<0 || d>=n){
return;
}
dodaj[l][s[d]-'a']++;
dodaj[d][s[l]-'a']++;
if(l-1<0 || d+1>=n){
return;
}
val=binary(l-1, d+1);
dodaj[l][s[d]-'a']+=val;
dodaj[d][s[l]-'a']+=val;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
precompute();
cin >> s;
n=s.size();
for(int i=0; i<n; i++){
pref[i+1]=sum(mul(pref[i], p), s[i]-'a');
suff[i+1]=sum(mul(suff[i], p), s[n-i-1]-'a');
}
for(int i=0; i<n; i++){
rijesi(i, 0);
rijesi(i, 1);
}
int val=0;
int upd=0;
for(int i=0; i<n; i++){
upd+=sw[i];
val-=upd;
oduz[i]+=val;
}
/* for(int i=0; i<n; i++){
cout << oduz[i] << " ";
}
cout << '\n';*/
for(int i=0; i<n; i++){
rijesi2(i, 0);
rijesi2(i, 1);
}
ll maksi=0;
for(int i=0; i<n; i++){
for(int j=0; j<p; j++){
maksi=max(maksi, oduz[i]+dodaj[i][j]);
}
}
cout << sol+maksi << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Correct |
1 ms |
768 KB |
Output is correct |
| 4 |
Correct |
2 ms |
768 KB |
Output is correct |
| 5 |
Correct |
1 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1536 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1792 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
25540 KB |
Output is correct |
| 2 |
Incorrect |
88 ms |
25548 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
