oj.uz

Submission #538757

# Submission time Handle Problem Language Result Execution time Memory
538757 2022-03-17T17:06:52 Z S2speed Palindromes (APIO14_palindrome) C++17
73 / 100
 425 ms 131072 KB 
#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 = 6e5 + 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();
		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();
		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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19156 KB Output is correct
2 Correct 13 ms 19156 KB Output is correct
3 Correct 13 ms 19148 KB Output is correct
4 Correct 13 ms 19156 KB Output is correct
5 Correct 13 ms 19156 KB Output is correct
6 Correct 15 ms 19156 KB Output is correct
7 Correct 13 ms 19120 KB Output is correct
8 Correct 13 ms 19156 KB Output is correct
9 Correct 15 ms 19156 KB Output is correct
10 Correct 13 ms 19156 KB Output is correct
11 Correct 13 ms 19072 KB Output is correct
12 Correct 13 ms 19124 KB Output is correct
13 Correct 13 ms 19156 KB Output is correct
14 Correct 13 ms 19064 KB Output is correct
15 Correct 16 ms 19156 KB Output is correct
16 Correct 13 ms 19044 KB Output is correct
17 Correct 13 ms 19156 KB Output is correct
18 Correct 14 ms 19156 KB Output is correct
19 Correct 13 ms 19156 KB Output is correct
20 Correct 14 ms 19160 KB Output is correct
21 Correct 13 ms 19156 KB Output is correct
22 Correct 13 ms 19108 KB Output is correct
23 Correct 14 ms 19132 KB Output is correct
24 Correct 14 ms 19140 KB Output is correct
25 Correct 13 ms 19152 KB Output is correct
26 Correct 14 ms 19132 KB Output is correct
27 Correct 15 ms 19156 KB Output is correct
28 Correct 13 ms 19156 KB Output is correct
29 Correct 13 ms 19192 KB Output is correct
30 Correct 13 ms 19152 KB Output is correct
31 Correct 13 ms 19088 KB Output is correct
32 Correct 13 ms 19156 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19356 KB Output is correct
2 Correct 14 ms 19524 KB Output is correct
3 Correct 15 ms 19412 KB Output is correct
4 Correct 14 ms 19412 KB Output is correct
5 Correct 16 ms 19440 KB Output is correct
6 Correct 14 ms 19364 KB Output is correct
7 Correct 15 ms 19432 KB Output is correct
8 Correct 16 ms 19440 KB Output is correct
9 Correct 16 ms 19332 KB Output is correct
10 Correct 15 ms 19396 KB Output is correct
11 Correct 15 ms 19400 KB Output is correct
12 Correct 16 ms 19412 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23532 KB Output is correct
2 Correct 29 ms 23072 KB Output is correct
3 Correct 29 ms 23444 KB Output is correct
4 Correct 28 ms 23352 KB Output is correct
5 Correct 32 ms 23168 KB Output is correct
6 Correct 31 ms 22892 KB Output is correct
7 Correct 30 ms 23148 KB Output is correct
8 Correct 35 ms 21916 KB Output is correct
9 Correct 34 ms 21908 KB Output is correct
10 Correct 32 ms 22732 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 63228 KB Output is correct
2 Correct 200 ms 59640 KB Output is correct
3 Correct 199 ms 64744 KB Output is correct
4 Correct 200 ms 70344 KB Output is correct
5 Correct 295 ms 60116 KB Output is correct
6 Correct 280 ms 65212 KB Output is correct
7 Correct 228 ms 62348 KB Output is correct
8 Correct 392 ms 44288 KB Output is correct
9 Correct 321 ms 48968 KB Output is correct
10 Correct 293 ms 60124 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 425 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -