Submission #230803

#	Time	Username	Problem	Language	Result	Execution time	Memory
230803		alishahali1382	Palindromes (APIO14_palindrome)	C++14	39 / 100	1097 ms	80896 KiB

palindrome

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
 
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=300010, LOG=21;
 
int n, m, k, u, v, x, y, t, a, b;
ll ans;
int Rank[MAXN<<1][LOG], P[MAXN<<1], pw;
int lcp[MAXN], L[MAXN], R[MAXN];
vector<int> seg[MAXN<<2];
string S;
 
inline bool cmp(int x, int y){
	if (Rank[x][pw-1]!=Rank[y][pw-1]) return Rank[x][pw-1]<Rank[y][pw-1];
	if (max(x, y)+(1<<(pw-1))>=m) return x>y;
	return Rank[x+(1<<(pw-1))][pw-1]<Rank[y+(1<<(pw-1))][pw-1];
}
 
void BuildSuffixArray(){
	for (int i=0; i<m; i++) Rank[i][0]=S[i], P[i]=i;
	for (pw=1; pw<LOG; pw++){
		sort(P, P+m, cmp);
		Rank[P[0]][pw]=0;
		for (int i=1; i<m; i++) Rank[P[i]][pw]=Rank[P[i-1]][pw] + cmp(P[i-1], P[i]);
	}
}
 
int GetLcp(int x, int y){
	if (x>y) swap(x, y);
	int res=0;
	for (int i=LOG-1; ~i; i--) if (y<m && Rank[x][i]==Rank[y][i]){
		x+=(1<<i);
		y+=(1<<i);
		res|=(1<<i);
	}
	return res;
}
 
void Add(int id, int tl, int tr, int l, int r, int val){
	if (r<=tl || tr<=l) return ;
	if (l<=tl && tr<=r){
		seg[id].pb(val);
		return ;
	}
	int mid=(tl+tr)>>1;
	Add(id<<1, tl, mid, l, r, val);
	Add(id<<1 | 1, mid, tr, l, r, val);
}
 
int GetPalindrome(int id, int tl, int tr, int pos, int val){
	if (pos<tl || tr<=pos) return 0;
	int res=0;
	if (seg[id].size() && seg[id][0]<val) res=(*--lower_bound(all(seg[id]), val))-2*pos+1;
	if (tr-tl==1) return res;
	int mid=(tl+tr)>>1;
	return max(res, max(GetPalindrome(id<<1, tl, mid, pos, val), GetPalindrome(id<<1 | 1, mid, tr, pos, val)));
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>S;
	n=S.size();
	S+="#";
	for (int i=n-1; ~i; i--) S+=S[i];
	m=S.size();
	BuildSuffixArray();
	/*
	debug(S)
	debug(GetLcp(0, 2*n))
	for (int i=0; i<m; i++) cerr<<P[i]<<" \n"[i==m-1];
	*/
	
	for (int i=0; i<n; i++){
		int len=GetLcp(i+1, 2*n-i);
		Add(1, 0, n, i+1-len, i+1, 2*i+1);
		ans=max(ans, 2ll*len);
	}
	for (int i=0; i<n; i++){
		int len=GetLcp(i, 2*n-i);
		Add(1, 0, n, i-len+1, i+1, 2*i);
		ans=max(ans, 2*len-1ll);
	}
	for (int i=0; i<4*MAXN; i++) sort(all(seg[i]));
	
	int ted=0;
	for (int i=0; i<m; i++) if (P[i]<n) P[ted++]=P[i];
	
	for (int i=0; i+1<n; i++) lcp[i]=GetLcp(P[i], P[i+1]);
	for (int i=0; i+1<n; i++) for (L[i]=i-1; ~L[i] && lcp[L[i]]>=lcp[i]; L[i]=L[L[i]]);
	for (int i=n-2; i; i--) for (R[i]=i+1; R[i]<n-1 && lcp[R[i]]>=lcp[i]; R[i]=R[R[i]]);
	for (int i=0; i<=n-2; i++){
		ll ted=(R[i]-L[i]);
		if (!ted) continue ;
		ans=max(ans, GetPalindrome(1, 0, n, P[i], 2*P[i]+lcp[i])*ted);
		//debug2(P[i], GetPalindrome(1, 0, n, P[i], 2*P[i]+lcp[i]))
	}
	cout<<ans<<'\n';
	
	return 0;
}

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