Submission #335699

#	Time	Username	Problem	Language	Result	Execution time	Memory
335699		alishahali1382	Palindromes (APIO14_palindrome)	C++14	100 / 100	659 ms	63476 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[LOG][MAXN<<1], P[MAXN<<1], P2[MAXN<<1], cnt[MAXN<<1];
int lcp[MAXN], L[MAXN], R[MAXN];
int seg[MAXN<<2];
int shit[MAXN<<1];
int f0[MAXN], f1[MAXN];
vector<pii> Q[MAXN<<1];
string S;
 
bool cmp(int x, int y, int pw){
	if (Rank[pw][x]!=Rank[pw][y]) return Rank[pw][x]<Rank[pw][y];
	if (max(x, y)+(1<<pw)>=m) return x>y;
	return Rank[pw][x+(1<<pw)]<Rank[pw][y+(1<<pw)]; 
}
void BuildSuffixArray(){
	for (int i=0; i<m; i++) P[i]=i;
	sort(P, P+m, [](int i, int j){ return S[i]<S[j];});
	for (int i=1; i<m; i++) Rank[0][P[i]]=Rank[0][P[i-1]]+(S[P[i-1]]<S[P[i]]);
	for (int j=0; j+1<LOG; j++){
		int x=0;
		for (int i=0; i<m; i++) if (P[i]+(1<<j)>=m) P2[x++]=P[i];
		for (int i=0; i<m; i++) if ((1<<j)<=P[i]) P2[x++]=P[i]-(1<<j);
		for (int i=0; i<m; i++) cnt[i]=0;
		for (int i=0; i<m; i++) cnt[Rank[j][i]]++;
		for (int i=1; i<m; i++) cnt[i]+=cnt[i-1];
		for (int i=m-1; ~i; i--) P[--cnt[Rank[j][P2[i]]]]=P2[i];
		for (int i=1; i<m; i++) Rank[j+1][P[i]]=Rank[j+1][P[i-1]] + cmp(P[i-1], P[i], j);
	}
}
int GetLcp(int x, int y){
	if (x<y) swap(x, y);
	int res=0;
	for (int i=LOG-1; ~i && x<m; i--) if (Rank[i][x]==Rank[i][y]){
		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("72", "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(clock())
	
	int l=-1, r=-1;
	for (int i=0; i<n; i++){
		if (i<=r) f0[i]=min(r-i+1, f0[2*l-i-1]);
		while (i+f0[i]<n && 0<=i-1-f0[i] && S[i+f0[i]]==S[i-1-f0[i]]) f0[i]++;
		if (i+f0[i]-1>r){
			l=i;
			r=i+f0[i]-1;
		}
	}
	l=r=-1;
	for (int i=0; i<n; i++){
		if (i<=r) f1[i]=min(r-i+1, f1[2*l-i]);
		while (i+1+f1[i]<n && 0<=i-1-f1[i] && S[i+1+f1[i]]==S[i-1-f1[i]]) f1[i]++;
		if (i+f1[i]-1>r){
			l=i;
			r=i+f1[i];
		}
	}
	for (int i=0; i<n; i++){
		int len=f0[i+1];
		ans=max(ans, 2ll*len);
		shit[2*i+1]=i+1-len;
	}
	for (int i=0; i<n; i++){
		int len=f1[i]+1;
		ans=max(ans, 2*len-1ll);
		shit[2*i]=i+1-len;
	}
	
	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);
		Maximize(shit[i], i+1, 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: 27 / 27