#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
const ll P1=313LL;
const ll P2=220721LL;
const ll M=1000LL*1000LL*1000LL+21LL;
const ll M2=1000000007LL;
char Wczytaj[N];
ll Potegi1[N];
ll Potegi2[N];
ll Hasz1[N][2];
ll Hasz2[N][2];
ll Plus[N][33];
ll Minus[N];
pair<ll, ll>CA[N];
ll wynik=0LL;
void LiczPotegi(){
Potegi1[0]=Potegi2[0]=1LL;
for(int i=1; i<N; i++){
Potegi1[i]=(Potegi1[i-1]*P1)%M;
Potegi2[i]=(Potegi2[i-1]*P2)%M2;
}
}
void WczytajDane(int &n){
string slowo;
getline(cin, slowo);
n=(int)slowo.size();
for(int i=1; i<=n; i++) Wczytaj[i]=slowo[i-1];
}
void LiczHasze(int n){
for(int i=1; i<=n; i++){
Hasz1[i][0]=( Hasz1[i-1][0]+Potegi1[i]*(ll)Wczytaj[i] )%M;
Hasz2[i][0]=( Hasz2[i-1][0]+Potegi2[i]*(ll)Wczytaj[i] )%M2;
}
for(int i=n; i>=1; i--){
Hasz1[i][1]=( Hasz1[i+1][1]+Potegi1[n-i+1]*(ll)Wczytaj[i] )%M;
Hasz2[i][1]=( Hasz2[i+1][1]+Potegi2[n-i+1]*(ll)Wczytaj[i] )%M2;
}
}
int CzyRowne(int p1, int k1, int p2, int k2, int n){
int h1, h2, h3, h4;
h1=(Hasz1[k1][0]-Hasz1[p1-1][0]+M)%M; h2=(Hasz2[k1][0]-Hasz2[p1-1][0]+M2)%M2;
h3=(Hasz1[p2][1]-Hasz1[k2+1][1]+M)%M; h4=(Hasz2[p2][1]-Hasz2[k2+1][1]+M2)%M2;
if( p1>n-k2+1 ){
h3=(h3*Potegi1[ p1-n+k2-1 ])%M;
h4=(h4*Potegi2[ p1-n+k2-1 ])%M2;
}
else{
h1=(h1*Potegi1[ n-k2+1-p1 ])%M;
h2=(h2*Potegi2[ n-k2+1-p1 ])%M2;
}
if(h1==h3 && h2==h4) return 1;
return 0;
}
int JakDaleko(int pl, int pp, int n){
int p, k, s;
if(pl<1 || pp>n || Wczytaj[pl]!=Wczytaj[pp]) return 0;
p=1; k=min(pl, n-pp+1);
while(p<k){
s=(p+k+1)/2;
if( CzyRowne(pl-s+1, pl, pp, pp+s-1, n) ) p=s;
else k=s-1;
}
return p;
}
void Dodaj(int p, int k, ll pw, ll roz){
CA[p].first+=pw; CA[p].second+=roz;
CA[k+1].first-=(pw+(ll)(k-p+1)*roz); CA[k+1].second-=roz;
}
void LiczPalindromyNieparzyste(int n){
int d, d2;
Minus[1]++; Minus[n]++;
wynik+=2LL;
for(int i=2; i<n; i++){
d=JakDaleko(i-1, i+1, n)+1;
wynik+=(ll)d;
Minus[i]-=(ll)(d-1);
Dodaj(i-d+1, i, 1LL, 1LL);
Dodaj(i+1, i+d-1, (ll)(d-1), -1LL);
d2=JakDaleko(i-d-1, i+d+1, n)+1;
if( i-d<1 || i+d>n ) continue;
Plus[i-d][ (int)Wczytaj[i+d]-96 ]+=(ll)d2;
Plus[i+d][ (int)Wczytaj[i-d]-96 ]+=(ll)d2;
}
}
void LiczPalindromyParzyste(int n){
int d, d2;
for(int i=1; i<n; i++){
if( Wczytaj[i]==Wczytaj[i+1] ){
d=JakDaleko(i, i+1, n);
Dodaj(i-d+1, i, 1LL, 1LL);
Dodaj(i+1, i+1+d-1, (ll)d, -1LL);
wynik+=(ll)d;
d2=JakDaleko(i-d-1, i+1+d+1, n)+1;
if( i-d<1 || i+d+1>n ) continue;
Plus[i-d][ (int)Wczytaj[i+d+1]-96 ]+=(ll)d2;
Plus[i+d+1][ (int)Wczytaj[i-d]-96 ]+=(ll)d2;
continue;
}
d=JakDaleko(i-1, i+2, n)+1;
Plus[i][ (int)Wczytaj[i+1]-96 ]+=(ll)d;
Plus[i+1][ (int)Wczytaj[i]-96 ]+=(ll)d;
}
}
void WyliczCA(int n){
pair<ll, ll> aktu=make_pair(0LL, 0LL);
for(int i=1; i<=n; i++){
aktu.first+=CA[i].first; aktu.second+=CA[i].second;
Minus[i]+=aktu.first;
aktu.first+=aktu.second;
}
}
ll Zamiana(int n){
ll wynik1=0LL;
for(int i=1; i<=n; i++){
for(int j=1; j<=30; j++){
if( j==(int)Wczytaj[i]-96 ) continue;
wynik1=max(wynik1, wynik-Minus[i]+Plus[i][j]+1LL);
}
}
return wynik1;
}
int main (){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
WczytajDane(n);
LiczPotegi();
LiczHasze(n);
LiczPalindromyNieparzyste(n);
LiczPalindromyParzyste(n);
WyliczCA(n);
cout<< max( Zamiana(n), wynik ) << "\n";
return 0;
}
| # |
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 |
4 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
33488 KB |
Output is correct |
| 2 |
Correct |
125 ms |
33436 KB |
Output is correct |
| 3 |
Correct |
138 ms |
33488 KB |
Output is correct |
| 4 |
Correct |
95 ms |
33564 KB |
Output is correct |
| 5 |
Correct |
92 ms |
33488 KB |
Output is correct |
| 6 |
Correct |
101 ms |
33564 KB |
Output is correct |
| 7 |
Correct |
91 ms |
33692 KB |
Output is correct |
| 8 |
Correct |
79 ms |
7708 KB |
Output is correct |
| 9 |
Correct |
81 ms |
33436 KB |
Output is correct |
| 10 |
Correct |
114 ms |
33436 KB |
Output is correct |
| 11 |
Correct |
123 ms |
33492 KB |
Output is correct |
| 12 |
Correct |
122 ms |
33428 KB |
Output is correct |
| 13 |
Correct |
143 ms |
33484 KB |
Output is correct |
| 14 |
Correct |
102 ms |
33436 KB |
Output is correct |
| 15 |
Correct |
129 ms |
33484 KB |
Output is correct |
| 16 |
Correct |
235 ms |
33572 KB |
Output is correct |
| 17 |
Correct |
52 ms |
33436 KB |
Output is correct |
| 18 |
Correct |
98 ms |
33376 KB |
Output is correct |
| 19 |
Correct |
50 ms |
33436 KB |
Output is correct |
