Submission #538741

#	Time	Username	Problem	Language	Result	Execution time	Memory
538741		S2speed	Palindromes (APIO14_palindrome)	C++17	23 / 100	123 ms	131072 KiB

palindrome

#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 = 1e3 + 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[i] = 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 , h;
mintree mt;
segtree st[2];
ll sf[maxn] , hs[maxn] , rh[maxn] , tv[maxn];
vector<ll> lcp;
vector<pair<string , ll>> v;

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){
	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 query(ll i , ll k){
	ll res = 0;
	for(ll j = i + k - 1 ; j >= i ; j--){
		if(is_palindrome(i , j)){
			res = j - i + 1;
			break;
		}
	}
	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;
}

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); s += '$';
	for(ll i = n - 1 ; ~i ; i--){
		h = s[i] + h;
		v.push_back({h , i});
	}
	sort(all(v));
	for(ll i = 0 ; i < n ; i++){
		sf[i] = v[i].second;
	}
	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]);
	}
	mt.init(n);
	mt.build(lcp);
	dv(0 , n);
	cout<<ans<<'\n';
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27