#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int, int >
#define F first
#define S second
#define int long long int
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;
/// khodaya komak kon
/// ya navid navid
/// ye tec khaphan ke yadam bemone : age jayi didi soale masir hamiltoni mikhad rasasho bokon yal oilery;https://mobomovie1.top/series/%D8%AF%D8%A7%D9%86%D9%84%D9%88%D8%AF-%D8%B3%D8%B1%DB%8C%D8%A7%D9%84-%D9%81%D8%B1%DB%8C%D9%86%D8%AC-fringe-2008-2013-%D8%A8%D8%A7-%D8%B2%D9%8A%D8%B1%D9%86%D9%88%D9%8A%D8%B3-%D9%81%D8%A7%D8%B1/
/// age ye ja mikhasti to dp az ozv i k ta entekhab koni bejash ye log bezan (nominal) hamoon 2**k va o 1 ent kon
const int N=1e5+100;
ll ph1[N];
ll ph2[N];
ll mod=1e9+7;
ll p[N];
ll a[N];
ll n;
ll inv[N];
char c[N];
ll b[N];
ll power(ll n,ll k){
if (k==0){
return 1;
}
if (k%2==1){
ll x=power(n,k/2);
return x*x%mod*n%mod;
}
ll x=power(n,k/2);
return x*x%mod;
}
ll h1(ll l,ll r){
ll z=ph1[r-1];
z-=ph1[l-1];
z+=mod;
z%=mod;
z*=inv[l-1];
z%=mod;
return z;
}
ll h2(ll l,ll r){
ll z=ph2[l];
z-=ph2[r];
z+=mod;
z%=mod;
z*=inv[n-r+1];
z%=mod;
return z;
}
ll bs(ll s,ll f){
ll l=0,r=min(s,n-f)+1;
while(r-l>1){
ll mid=(r+l)/2;
ll z=h1(s-mid+1,s+1);
ll w=h2(f+1,f+mid+1);
if (z==w){
l=mid;
}
else{
r=mid;
}
}
return l;
}
ll ans[N][30];
ll g[N];
ll baze1[N],baze2[N];
ll baze3[N],baze4[N],baze5[N],baze6[N];
int32_t main(){
p[0]=1;
inv[0]=1;
for (int i=1;i<N;i++){
p[i]=p[i-1]*311%mod;
inv[i]=power(p[i],mod-2);
}
cin >> n;
for (int i=0;i<n;i++){
cin >> c[i];
a[i]=c[i]-'a'+1;
}
for (int i=1;i<=n;i++){
ph1[i]=ph1[i-1]%mod+a[i-1]*p[i-1]%mod;
ph1[i]%=mod;
}
for (int i=n;i>0;i--){
ph2[i]=ph2[i+1]+a[i-1]*p[n-i]%mod;
ph2[i]%=mod;
}
ll u=1;
for (int i=1;i<n;i++){
ll d=bs(i,i);
baze1[i]+=d;
baze5[i-d]++;
baze3[i]++;
//cout << d << endl;
// baze1.pb({i-d,i});
baze2[i]+=d;
baze6[i]++;
baze4[i+d]+=1;
// baze2.pb({i,i+d});
u+=d;
if (i-d>0 && i+d<=n-1){
ll w=bs(i-d-1,i+d+1);
ans[i-d-1][a[i+d]]+=w+1;
ans[i+d][a[i-d-1]]+=w+1;
// cout << i << " " << w << " " << a[i-d-1] << " " << a[i+d] << " " << d << endl;
}
d=bs(i,i+1);
u+=d+1;
baze1[i]+=d;
baze5[i-d]++;
baze3[i]+=1;
baze2[i+1]+=d;
baze4[i+d+1]++;
baze6[i+1]++;
//baze1.pb({i-d,i});
// baze2.pb({i+1,i+d+1});
// cout << i << " " << d << endl;
if (i-d>0 && i+1+d<=n-1){
ll w=bs(i-d-1,i+1+d+1);
ans[i-d-1][a[i+d+1]]+=w+1;
ans[i+d+1][a[i-d-1]]+=w+1;
// cout << i << " : " << w << " " << a[i-d-1] << " " << a[i+d+1] << endl;
}
}
ll cnt1=0,cnt2=0;
ll b1=0,b2=0;
ll sum=0;
for (int i=0;i<n;i++){
b1-=baze3[i];
// b2-=baze4[i];
sum-=baze1[i];
b1+=baze5[i];
sum+=b1;
sum-=b2;
b2+=baze6[i];
sum+=baze2[i];
b2-=baze4[i];
g[i]=sum;
//cout << i << " " << sum << " " << ans[i][1] << endl;
}
ll ma=0;
for (int i=0;i<n;i++){
for (int j=0;j<29;j++){
ma=max(ma,ans[i][j]-g[i]);
// cout << i << " df " << j << " " << ans[i][j] << " " << g[i] << endl;
}
}
cout << u+ma << endl;
}
Compilation message
palinilap.cpp: In function 'int32_t main()':
palinilap.cpp:136:8: warning: unused variable 'cnt1' [-Wunused-variable]
ll cnt1=0,cnt2=0;
^~~~
palinilap.cpp:136:15: warning: unused variable 'cnt2' [-Wunused-variable]
ll cnt1=0,cnt2=0;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
1872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
1912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
1912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
