oj.uz

Submission #538765

# Submission time Handle Problem Language Result Execution time Memory
538765 2022-03-17T17:36:59 Z S2speed Palindromes (APIO14_palindrome) C++17
73 / 100
 1000 ms 92692 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

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

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

struct segtree {

	int sz = 1;
	vector<int> val;

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

	void build(vector<int> &a , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < sze(a)){
				val[x] = a[lx];
			}
			return;
		}
		int 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<int> &a){
		build(a , 0 , 0 , sz);
		return;
	}

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

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

};

int n;
string s;
segtree st[2];
ll hs[maxn] , rh[maxn] , tv[maxn];
int sf[maxn] , bt[maxn];
vector<int> lcp;
pii rmq[maxn][20];

void rmq_build(){
	for(int i = 0 ; i < n - 1 ; i++){
		rmq[i][0] = {lcp[i] , i};
	}
	for(int j = 0 ; j < 19 ; j++){
		int lm = n - 1 - (1 << j);
		if(lm < 0) break;
		for(int i = 0 , o = (1 << j) ; i < lm ; i++ , o++){
			rmq[i][j + 1] = min(rmq[i][j] , rmq[o][j]);
		}
		for(int i = lm ; i < n - 1 ; i++){
			rmq[i][j + 1] = rmq[i][j];
		}
	}
	bt[1] = 0;
	int h = 1 , z = 0;
	for(int i = 2 ; i < maxn ; i++){
		if(i == (h << 1)){
			h = i;
			z++;
		}
		bt[i] = z;
	}
	return;
}

int hum = -1;
int get_hash(int l , int 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(int l , int r){
	if(l < 0 || r >= n) return false;
	ll h = get_hash(l , r);
	ll o = rh[r] - (l ? rh[l - 1] : 0);
	o %= md; o += (o < 0) * md;
	h *= tv[l]; h %= md;
	return (h == o);
}

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

int t[maxn][2];

ll query(int i , int k){
	if(k < 2) return k;
	int res = 0;
	int l = i , r = i + (k + 1) / 2;
	int 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(int l , int r){
	if(l == r - 1){
		ans = max(ans , query(sf[l] , n - sf[l]));
	}
	if(l >= r - 1) return;
	int ln = r - l - 1;
	pii h = min(rmq[l][bt[ln]] , rmq[r - 1 - (1 << bt[ln])][bt[ln]]);
	int k = h.first , m = h.second + 1;
	ans = max(ans , 1ll * (r - l) * query(sf[l] , k));
	dv(l , m); dv(m , r);
	return;
}

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

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

vector<int> a;

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

	tv[0] = 1;
	for(int i = 1 ; i < maxn ; i++){
		tv[i] = tv[i - 1] * P % md;
	}
	cin>>s; n = sze(s);
	for(int i = 0 ; i < n ; i++){
		rnk[i] = s[i] - 'a' + 1;
	}
	int lm = max(27 , n + 1);
	for(int j = 0 ; j < 19 ; j++){
		v.clear();
		for(int i = 0 ; i < lm ; i++){
			cnt[i].clear(); cnt[i].shrink_to_fit();
		}
		for(int i = 0 ; i < n ; i++){
			int o = i + (1 << j);
			rhk[i] = (o >= n ? 0 : rnk[o]);
			cnt[rhk[i]].push_back(i);
		}
		for(int e = 0 ; e < lm ; e++){
			for(auto i : cnt[e]){
				v.push_back(i);
			}
		}
		for(int i = 0 ; i < lm ; i++){
			cnt[i].clear(); cnt[i].shrink_to_fit();
		}
		for(auto i : v){
			cnt[rnk[i]].push_back(i);
		}
		int cur = 0;
		for(int e = 0 ; e < lm ; e++){
			int pr = -1;
			for(auto i : cnt[e]){
				int u = rhk[i];
				if(pr != u){
					cur++; pr = u;
				}
				rnk[i] = cur;
			}
		}
	}
	for(int i = 0 ; i < n ; i++){
		sf[rnk[i] - 1] = i;
	}
	rh[0] = hs[0] = s[0];
	for(int 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(int e = 0 ; e < n - 1 ; e++){
		lcp[e] = get_lcp(sf[e] , sf[e + 1]);
	}
	st[0].init(n); st[1].init(n);
	for(int i = 0 ; i < n ; i++){
		t[i][0] = cal_t(i , 0);
		a.push_back(t[i][0]);
		t[i][1] = cal_t(i , 1);
	}
	st[0].build(a);
	a.clear();
	for(int i = 0 ; i < n ; i++){
		a.push_back(t[i][1]);
	}
	st[1].build(a);
	rmq_build();
	dv(0 , n);
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10836 KB Output is correct
2 Correct 10 ms 10836 KB Output is correct
3 Correct 8 ms 10876 KB Output is correct
4 Correct 10 ms 10812 KB Output is correct
5 Correct 8 ms 10896 KB Output is correct
6 Correct 8 ms 10836 KB Output is correct
7 Correct 10 ms 10836 KB Output is correct
8 Correct 8 ms 10936 KB Output is correct
9 Correct 7 ms 10836 KB Output is correct
10 Correct 7 ms 10836 KB Output is correct
11 Correct 7 ms 10836 KB Output is correct
12 Correct 7 ms 10836 KB Output is correct
13 Correct 7 ms 10856 KB Output is correct
14 Correct 7 ms 10836 KB Output is correct
15 Correct 10 ms 10836 KB Output is correct
16 Correct 8 ms 10836 KB Output is correct
17 Correct 8 ms 10836 KB Output is correct
18 Correct 7 ms 10888 KB Output is correct
19 Correct 10 ms 10836 KB Output is correct
20 Correct 8 ms 10836 KB Output is correct
21 Correct 8 ms 10836 KB Output is correct
22 Correct 8 ms 10836 KB Output is correct
23 Correct 10 ms 10872 KB Output is correct
24 Correct 9 ms 10836 KB Output is correct
25 Correct 8 ms 10836 KB Output is correct
26 Correct 9 ms 10856 KB Output is correct
27 Correct 8 ms 10948 KB Output is correct
28 Correct 8 ms 10836 KB Output is correct
29 Correct 8 ms 10836 KB Output is correct
30 Correct 9 ms 10836 KB Output is correct
31 Correct 9 ms 10836 KB Output is correct
32 Correct 8 ms 10844 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11092 KB Output is correct
2 Correct 10 ms 11184 KB Output is correct
3 Correct 9 ms 11092 KB Output is correct
4 Correct 10 ms 11188 KB Output is correct
5 Correct 10 ms 11192 KB Output is correct
6 Correct 9 ms 11092 KB Output is correct
7 Correct 10 ms 11204 KB Output is correct
8 Correct 10 ms 11192 KB Output is correct
9 Correct 11 ms 11204 KB Output is correct
10 Correct 11 ms 11072 KB Output is correct
11 Correct 10 ms 11092 KB Output is correct
12 Correct 10 ms 11092 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 13648 KB Output is correct
2 Correct 29 ms 13780 KB Output is correct
3 Correct 24 ms 13600 KB Output is correct
4 Correct 24 ms 13656 KB Output is correct
5 Correct 30 ms 13592 KB Output is correct
6 Correct 34 ms 13620 KB Output is correct
7 Correct 27 ms 13716 KB Output is correct
8 Correct 41 ms 13672 KB Output is correct
9 Correct 38 ms 13616 KB Output is correct
10 Correct 32 ms 13648 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 36644 KB Output is correct
2 Correct 222 ms 37140 KB Output is correct
3 Correct 183 ms 36992 KB Output is correct
4 Correct 192 ms 40676 KB Output is correct
5 Correct 353 ms 36684 KB Output is correct
6 Correct 284 ms 37480 KB Output is correct
7 Correct 327 ms 37352 KB Output is correct
8 Correct 557 ms 36724 KB Output is correct
9 Correct 482 ms 36624 KB Output is correct
10 Correct 340 ms 37084 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 90956 KB Output is correct
2 Correct 733 ms 92692 KB Output is correct
3 Correct 627 ms 90884 KB Output is correct
4 Correct 691 ms 91864 KB Output is correct
5 Execution timed out 1097 ms 90748 KB Time limit exceeded
6 Halted 0 ms 0 KB -