#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()
const int mod = 998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e5 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int base = 31;
string s;
int pw[MAXN], n;
ll ans, delt[MAXN][26];
//1 2 3 ... k
struct tournament{
ll p[trsz], seg[trsz];
int ad;
void prop(int x, int lo, int hi){
if(p[x] == 0) return;
ll num = (hi - lo);
seg[x] += p[x] * num;
seg[x] += num * (num - 1) / (ll)2;
if(x < off){
int mid = (lo + hi) / 2;
p[x * 2] += p[x];
p[x] += (mid - lo);
p[x * 2 + 1] += p[x];
}
p[x] = 0;
}
void update(int x, int lo, int hi, int a, int b){
prop(x, lo, hi);
if(lo >= b or hi <= a) return;
if(lo >= a and hi <= b){
p[x] = ad;
ad += (hi - lo);
prop(x, lo, hi);
return;
}
int mid = (lo + hi) / 2;
update(x * 2, lo, mid, a, b);
update(x * 2 + 1, mid, hi, a, b);
seg[x] = seg[x * 2] + seg[x * 2 + 1];
}
void upd(int l, int r){
ad = 1;
update(1, 0, off, l, r);
}
ll query(int x, int lo, int hi, int a, int b){
prop(x, lo, hi);
if(lo >= b or hi <= a) return 0;
if(lo >= a and hi <= b) return seg[x];
int mid = (lo + hi) / 2;
return query(x * 2, lo, mid, a, b) + query(x * 2 + 1, mid, hi, a, b);
}
}t1;
//k k-1 k-2 .. 1
struct tournament2{
ll p[trsz], seg[trsz];
int ad;
void prop(int x, int lo, int hi){
if(p[x] == 0) return;
ll num = (hi - lo);
seg[x] += p[x] * num;
seg[x] += num * (num - 1) / (ll)2;
if(x < off){
int mid = (lo + hi) / 2;
p[x * 2 + 1] += p[x];
p[x] += (mid - lo);
p[x * 2] += p[x];
}
p[x] = 0;
}
void update(int x, int lo, int hi, int a, int b){
prop(x, lo, hi);
if(lo >= b or hi <= a) return;
if(lo >= a and hi <= b){
p[x] = ad;
ad += (hi - lo);
prop(x, lo, hi);
return;
}
int mid = (lo + hi) / 2;
update(x * 2 + 1, mid, hi, a, b);
update(x * 2, lo, mid, a, b);
seg[x] = seg[x * 2] + seg[x * 2 + 1];
}
void upd(int l, int r){
ad = 1;
update(1, 0, off, l, r);
}
ll query(int x, int lo, int hi, int a, int b){
prop(x, lo, hi);
if(lo >= b or hi <= a) return 0;
if(lo >= a and hi <= b) return seg[x];
int mid = (lo + hi) / 2;
return query(x * 2, lo, mid, a, b) + query(x * 2 + 1, mid, hi, a, b);
}
}t2;
int add(int a, int b){
a += b;
if(a >= mod) a -= mod;
return a;
}
int sub(int a, int b){
a -= b;
if(a < 0) a += mod;
return a;
}
int mul(ll a, ll b){
return (a * b) % mod;
}
struct hash{
vi pf;
void init(string ss){
pf.clear();
pf.PB(0);
for(int i=1; i<=(int)ss.size(); i++) pf.PB(add(pf.back(), mul(pw[i], ss[i - 1] - 'a')));
}
int gval(int l, int r){
return mul(pw[MAXN - 1 - l], sub(pf[r], pf[l - 1]));
}
}h1, h2;
int vl(int l, int r, bool rev){
if(rev){
swap(l, r);
l = n + 1 - l;
r = n + 1 - r;
return h2.gval(l, r);
}
return h1.gval(l, r);
}
int palin(int l, int r){
return vl(l, r, 0) == vl(l, r, 1);
}
void neparni(){
for(int i=1; i<=n; i++){
int lo = 1, hi = n, ret = 0;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(i - mid < 1 or i + mid > n){
hi = mid - 1;
continue;
}
if(palin(i - mid, i + mid)) lo = mid + 1, ret = mid;
else hi = mid - 1;
}
ans += ret + 1;
int l1 = i - ret - 1, r1 = i + ret + 1;
t1.upd(l1 + 1, i);
t2.upd(i + 1, r1);
if(l1 == 0 or r1 == n + 1) continue;
//l2 r2
lo = 1, hi = n, ret = 0;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(l1 - mid < 1 or r1 + mid > n){
hi = mid - 1;
continue;
}
if(vl(l1 - mid, l1 - 1, 0) == vl(r1 + 1, r1 + mid, 1)) lo = mid + 1, ret = mid;
else hi = mid - 1;
}
delt[l1][s[r1 - 1] - 'a'] += ret + 1;
delt[r1][s[l1 - 1] - 'a'] += ret + 1;
}
}
void parni(){
for(int i=1; i<n; i++){
int l1, r1, lo, hi, ret;
if(s[i - 1] != s[i]){
l1 = i;
r1 = i + 1;
}else{
lo = 1, hi = n, ret = 0;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(i - mid < 1 or i + 1 + mid > n){
hi = mid - 1;
continue;
}
if(palin(i - mid, i + 1 + mid)) lo = mid + 1, ret = mid;
else hi = mid - 1;
}
ans += ret + 1;
l1 = i - ret - 1, r1 = i + 1 + ret + 1;
t1.upd(l1 + 1, i + 1);
t2.upd(i + 1, r1);
}
if(l1 == 0 or r1 == n + 1) continue;
lo = 1, hi = n, ret = 0;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(l1 - mid < 1 or r1 + mid > n){
hi = mid - 1;
continue;
}
if(vl(l1 - mid, l1 - 1, 0) == vl(r1 + 1, r1 + mid, 1)) lo = mid + 1, ret = mid;
else hi = mid - 1;
}
delt[l1][s[r1 - 1] - 'a'] += ret + 1;
delt[r1][s[l1 - 1] - 'a'] += ret + 1;
}
}
void solve(){
pw[0] = 1;
for(int i=1; i<MAXN; i++) pw[i] = mul(pw[i - 1], base);
cin >> s;
n = s.size();
h1.init(s);
reverse(all(s));
h2.init(s);
reverse(all(s));
neparni();
parni();
ll cans = ans;
for(int i=1; i<=n; i++){
for(int let=0; let<26; let++) cans = max(cans, delt[i][let] + ans);
}
cout << cans << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
//cin >> tt;
while(tt--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
17492 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
17244 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
49864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
