Submission #538769

#	Time	Username	Problem	Language	Result	Execution time	Memory
538769		S2speed	Palindromes (APIO14_palindrome)	C++11	73 / 100	1099 ms	55348 KiB

palindrome

#include<bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("avx2")
 
#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 mintree {
 
	int sz = 1;
	vector<pii> val;
	pii def;
 
	void init(int n){
		while(sz < n) sz <<= 1;
		def = {inf , -1};
		val.assign(sz << 1 , def);
		return;
	}
 
	void build(vector<int> &a , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < sze(a)){
				val[x] = {a[lx] , 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;
	}
 
	pii cal(int l , int r , int x , int lx , int rx){
		if(rx <= l || lx >= r) return def;
		if(rx <= r && lx >= l) return val[x];
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		pii a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
		return min(a , b);
	}
 
	pii cal(int l , int r){
		return cal(l , r , 0 , 0 , sz);
	}
 
};
 
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;
mintree mt;
segtree st[2];
ll hs[maxn] , rh[maxn] , tv[maxn];
int sf[maxn];
vector<int> lcp;
 
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;
	pii h = mt.cal(l , r - 1);
	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);
	mt.init(n);
	mt.build(lcp);
	dv(0 , n);
	cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

palindrome.cpp:6:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
    6 | #pragma GCC optimize("avx2")
      |                            ^
palindrome.cpp:22:17: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   22 |  void init(int n){
      |                 ^
palindrome.cpp:29:53: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   29 |  void build(vector<int> &a , int x , int lx , int rx){
      |                                                     ^
palindrome.cpp:41:27: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   41 |  void build(vector<int> &a){
      |                           ^
palindrome.cpp:46:49: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   46 |  pii cal(int l , int r , int x , int lx , int rx){
      |                                                 ^
palindrome.cpp:54:23: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   54 |  pii cal(int l , int r){
      |                       ^
palindrome.cpp:65:17: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   65 |  void init(int n){
      |                 ^
palindrome.cpp:71:53: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   71 |  void build(vector<int> &a , int x , int lx , int rx){
      |                                                     ^
palindrome.cpp:83:27: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   83 |  void build(vector<int> &a){
      |                           ^
palindrome.cpp:88:57: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   88 |  int cal(int l , int r , int k , int x , int lx , int rx){
      |                                                         ^
palindrome.cpp:98:31: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   98 |  int cal(int l , int r , int k){
      |                               ^
palindrome.cpp:113:27: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  113 | int get_hash(int l , int r){
      |                           ^
palindrome.cpp:120:33: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  120 | bool is_palindrome(int l , int r){
      |                                 ^
palindrome.cpp:129:26: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  129 | int get_lcp(int i , int j){
      |                          ^
palindrome.cpp:144:23: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  144 | ll query(int i , int k){
      |                       ^
palindrome.cpp:163:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  163 | void dv(int l , int r){
      |                      ^
palindrome.cpp:178:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  178 | int cal_t(int i , bool j){
      |                         ^
palindrome.cpp:193:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  193 | int main(){
      |          ^

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