Submission #230864

#	Time	Username	Problem	Language	Result	Execution time	Memory
230864		alishahali1382	Palindromes (APIO14_palindrome)	C++14	73 / 100	1098 ms	119776 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=19;
 
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];
int seg[MAXN<<2];
int shit[MAXN<<1];
int rad[MAXN<<1], cnt[MAXN<<1];
vector<pii> vec[MAXN<<1], Q[MAXN<<1];
string S;
 
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];
}

inline void radix(){
	memset(cnt, 0, sizeof(cnt));
	for (int i=0; i<m; i++) cnt[shit[rad[i]=P[i]]]++;/*, mx=max(mx, shit[P[i]]);*/
	int mx=0;
	while (cnt[mx]!=m) cnt[mx+1]+=cnt[mx], mx++;
	for (int i=m-1; ~i; i--) P[--cnt[shit[rad[i]]]]=rad[i];
}

void BuildSuffixArray(){
	for (int i=0; i<m; i++) Rank[i][0]=S[i], P[i]=i;
	for (pw=1; pw<LOG; pw++){
		for (int i=0; i<m; i++) shit[i]=(i+(1<<(pw-1))>=m?0:Rank[i+(1<<(pw-1))][pw-1]);
		radix();
		for (int i=0; i<m; i++) shit[i]=Rank[i][pw-1];
		radix();
		
		//sort(P, P+m, cmp);
		Rank[P[0]][pw]=1;
		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 Maximize(int l, int r, int val){
	for (l+=n, r+=n; l<r; l>>=1, r>>=1){
		if (l&1) seg[l++]=val;
		if (r&1) seg[--r]=val;
	}
}

int Get(int pos){
	int res=-1;
	for (pos+=n; pos; pos>>=1) res=max(res, seg[pos]);
	return res;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("66", "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();
	
	for (int i=0; i<n; i++){
		int len=GetLcp(i+1, 2*n-i);
		ans=max(ans, 2ll*len);
		vec[2*i+1].pb({i+1-len, i+1});
	}
	for (int i=0; i<n; i++){
		int len=GetLcp(i, 2*n-i);
		ans=max(ans, 2*len-1ll);
		vec[2*i].pb({i-len+1, i+1});
	}
	
	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 ;
		Q[2*P[i]+lcp[i]].pb({P[i], ted});
	}
	memset(seg, -1, sizeof(seg));
	for (int i=0; i<2*n; i++){
		for (pii p:Q[i]) ans=max(ans, (Get(p.first)-2*p.first+1ll)*p.second);
		for (pii p:vec[i]) Maximize(p.first, p.second, i);
	}
	cout<<ans<<'\n';
	
	return 0;
}
/*
abaa

*/

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