제출 #538758

#제출 시각아이디문제언어결과실행 시간메모리
538758S2speed회문 (APIO14_palindrome)C++17
73 / 100
1085 ms80368 KiB
#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 3e5 + 16 , P = 131 , md = 2000000357 , inf = 2e16;

struct mintree {

	ll sz = 1;
	vector<pll> val;
	pll def;

	void init(ll n){
		while(sz < n) sz <<= 1;
		def = {inf , -1};
		val.assign(sz << 1 , def);
		return;
	}

	void build(vector<ll> &a , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			if(lx < sze(a)){
				val[x] = {a[lx] , lx};
			}
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(a , ln , lx , m); build(a , rn , m , rx);
		val[x] = min(val[ln] , val[rn]);
	}

	void build(vector<ll> &a){
		build(a , 0 , 0 , sz);
		return;
	}

	pll cal(ll l , ll r , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return def;
		if(rx <= r && lx >= l) return val[x];
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		pll a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
		return min(a , b);
	}

	pll cal(ll l , ll r){
		return cal(l , r , 0 , 0 , sz);
	}

};

struct segtree {

	ll sz = 1;
	vector<ll> val;

	void init(ll n){
		while(sz < n) sz <<= 1;
		val.assign(sz << 1 , inf);
		return;
	}

	void set(ll i , ll k , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			val[x] = k;
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(i < m){
			set(i , k , ln , lx , m);
		} else {
			set(i , k , rn , m , rx);
		}
		val[x] = min(val[ln] , val[rn]);
		return;
	}

	void set(ll i , ll k){
		set(i , k , 0 , 0 , sz);
		return;
	}

	ll cal(ll l , ll r , ll k , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return -1;
		if(val[x] > k) return -1;
		if(rx - lx == 1) return lx;
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		ll a = cal(l , r , k , rn , m , rx);
		if(a != -1) return a;
		return cal(l , r , k , ln , lx , m);
	}

	ll cal(ll l , ll r , ll k){
		return cal(l , r , k , 0 , 0 , sz);
	}

};

ll n;
string s;
mintree mt;
segtree st[2];
ll sf[maxn] , hs[maxn] , rh[maxn] , tv[maxn];
vector<ll> lcp;

ll hum = -1;
ll get_hash(ll l , ll r){
	if(r >= n) return hum--;
	ll res = hs[r] - (l ? tv[r - l + 1] * hs[l - 1] : 0);
	res %= md; res += (res < 0) * md;
	return res;
}

bool is_palindrome(ll l , ll r){
	if(l < 0 || r >= n) return false;
	ll h = hs[r] - (l ? tv[r - l + 1] * hs[l - 1] : 0);
	h %= md; h += (h < 0) * md;
	ll o = rh[r] - (l ? rh[l - 1] : 0);
	o %= md; o += (o < 0) * md;
	h *= tv[l]; h %= md;
	return (h == o);
}

ll get_lcp(ll i , ll j){
	ll l = 0 , r = n;
	while(l < r - 1){
		ll m = (r + l) >> 1;
		if(get_hash(i , i + m - 1) == get_hash(j , j + m - 1)){
			l = m;
		} else {
			r = m;
		}
	}
	return l;
}

ll t[maxn][2];

ll query(ll i , ll k){
	if(k < 2) return k;
	ll res = 0;
	ll l = i , r = i + (k + 1) / 2;
	ll h = st[0].cal(l , r , i);
	if(h != -1){
		res = max(res , 2 * (h - i) + 1);
	}
	r = i + k / 2;
	h = st[1].cal(l , r , i);
//	cout<<l<<' '<<r<<' '<<i<<' '<<t[l][1]<<' '<<h<<'\n';
	if(h != -1){
		res = max(res , 2 * (h - i) + 2);
	}
	return res;
}

ll ans = 0;

void dv(ll l , ll r){
	if(l == r - 1){
		ans = max(ans , query(sf[l] , n - sf[l]));
	}
	if(l >= r - 1) return;
	pll h = mt.cal(l , r - 1);
	ll k = h.first , m = h.second + 1;
	ans = max(ans , (r - l) * query(sf[l] , k));
	dv(l , m); dv(m , r);
	return;
}

ll rnk[maxn] , rhk[maxn];
vector<pll> cnt[maxn] , v;

ll cal_t(ll i , bool j){
	ll l = -1 , r = i + j;
	while(l < r - 1){
		ll m = (r + l) >> 1;
		if(is_palindrome(m , i + i - m + j)){
			r = m;
		} else {
			l = m;
		}
	}
	return r;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	tv[0] = 1;
	for(ll i = 1 ; i < maxn ; i++){
		tv[i] = tv[i - 1] * P % md;
	}
	cin>>s; n = sze(s);
	for(ll i = 0 ; i < n ; i++){
		rnk[i] = s[i] - 'a' + 1;
	}
	ll lm = max(27ll , n + 1);
	for(ll j = 0 ; j < 20 ; j++){
		v.clear();
		for(ll i = 0 ; i < lm ; i++){
			cnt[i].clear(); cnt[i].shrink_to_fit();
		}
		for(ll i = 0 ; i < n ; i++){
			ll o = i + (1 << j);
			rhk[i] = (o >= n ? 0 : rnk[o]);
			cnt[rhk[i]].push_back({rnk[i] , i});
		}
		for(ll i = 0 ; i < lm ; i++){
			for(auto p : cnt[i]){
				v.push_back(p);
			}
		}
		for(ll i = 0 ; i < lm ; i++){
			cnt[i].clear(); cnt[i].shrink_to_fit();
		}
		for(auto p : v){
			ll i = p.second;
			cnt[rnk[i]].push_back({rhk[i] , i});
		}
		ll cur = 0;
		for(ll e = 0 ; e < lm ; e++){
			ll pr = -1;
			for(auto p : cnt[e]){
				ll i = p.second , u = p.first;
				if(pr != u){
					cur++; pr = u;
				}
				rnk[i] = cur;
			}
		}
	}
	for(ll i = 0 ; i < n ; i++){
		sf[rnk[i] - 1] = i;
	}
	rh[0] = hs[0] = s[0];
	for(ll i = 1 ; i < n ; i++){
		hs[i] = P * hs[i - 1] + s[i]; hs[i] %= md;
		rh[i] = rh[i - 1] + tv[i] * s[i]; rh[i] %= md;
	}
	lcp.resize(n - 1);
	for(ll e = 0 ; e < n - 1 ; e++){
		lcp[e] = get_lcp(sf[e] , sf[e + 1]);
	}
	st[0].init(n); st[1].init(n);
	for(ll i = 0 ; i < n ; i++){
		t[i][0] = cal_t(i , 0);
		st[0].set(i , t[i][0]);
		t[i][1] = cal_t(i , 1);
		st[1].set(i , t[i][1]);
	}
	mt.init(n);
	mt.build(lcp);
	dv(0 , n);
	cout<<ans<<'\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...