Submission #532881

#	Time	Username	Problem	Language	Result	Execution time	Memory
532881		codr0	Palindromes (APIO14_palindrome)	C++14	73 / 100	1063 ms	56828 KiB

palindrome

// Code by Parsa Eslami
 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define bit(i,j) ((j>>i)&1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
 
using namespace std;
const int N=3e5+4;
const int LG=20;
string s;
int n;
int arr[2*N];
int PAL[2*N];
int pw[LG];
int rnk[LG][N];
int rnkR[LG][N];

	int lcp(int I,int J){
		int rt=0;
		FORR(j,LG-1,0) if(max(I,J)+pw[j]<=(n+1)&&rnk[j][I]==rnk[j][J]){
			I+=pw[j];
			J+=pw[j];
			rt+=pw[j];
		}
		return rt;
	}

	int pal(int l,int r){
		int rt=0;
		FORR(j,LG-1,0)
			if((r+pw[j])<=(n+1)&&(l-pw[j])>=0&&rnkR[j][l]==rnk[j][r]){
				rt+=pw[j];
				l-=pw[j];
				r+=pw[j];
			}
		return rt;
	}

	bool cmp(int i,int j){
		int t=lcp(i,j);
		i+=t;
		j+=t;
		if(i==n+1) return 1;
		if(j==n+1) return 0;
		return (s[i]<s[j]);
	}

	int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	pw[0]=1; FOR(i,1,LG-1) pw[i]=pw[i-1]*2;
	cin>>s; n=SZ(s);
	s='$'+s;
	FOR(i,1,n) rnk[0][i]=rnkR[0][i]=s[i]-'a';
	FOR(j,1,LG-1){
		vector<pair<pii,int>> vc;
		FOR(i,1,n-pw[j]+1){
			vc.pb({{rnk[j-1][i],rnk[j-1][i+pw[j-1]]},2*i});
		}
		FOR(i,pw[j],n){
			vc.pb({{rnkR[j-1][i],rnkR[j-1][i-pw[j-1]]},2*i+1});
		}
		sort(all(vc));
		int pr=0;
		FOR(i,0,SZ(vc)-1){
			if(i==0||vc[i].F!=vc[i-1].F) pr++;
			int I=vc[i].S/2;
			if(vc[i].S%2==0) rnk[j][I]=pr;
			else rnkR[j][I]=pr;
		}
	}
	int sa[n+1];
	FOR(i,1,n) sa[i]=i;
	sort(sa+1,sa+n+1,cmp);
	int to[n+1]; FOR(i,1,n) to[sa[i]]=i;
	int num[2*n]={};
	FOR(i,1,n){
		num[2*i-1]=pal(i,i);
		if(i!=n) num[2*i]=pal(i,i+1);
	}
	FOR(i,1,n){
		arr[2*i-1]=n+1-sa[i];
		if(i!=n) arr[2*i]=lcp(sa[i],sa[i+1]);
	}
	FOR(i,1,n){
		num[2*i-1]-=i;
		if(i!=n) num[2*i]-=i;
	}
	vector<int> ind[2*n];
	FOR(i,1,2*n-1) ind[num[i]+n].pb(i);
	set<int> st;
	FOR(j,n+1,2*n-1) for(int x0:ind[j]) st.insert(x0);
	st.insert(2*n+1);
	FOR(i,1,n){
		for(int x0:ind[n+1-i]) st.insert(x0);
		int mid=0;
		mid=(i+n)/2;
		if((i+n)%2==0){
			mid=mid*2-1;
		}else{
			mid=mid*2;
		}
		auto it=st.lower_bound(mid+1);
		it--;
		PAL[2*to[i]-1]=(*it)-(2*i-1)+1;
		if(to[i]!=n&&arr[2*to[i]]){
			int X=i+arr[2*to[i]]-1;
			mid=(i+X)/2;
			if((i+X)%2==0){
				mid=mid*2-1;
			}else mid=mid*2;
			it=st.lower_bound(mid+1);
			it--;
			PAL[2*to[i]]=(*it)-(2*i-1)+1;
		}
	}
	vector<pair<pii,int>> vc;
	FOR(i,1,2*n-1){
		vc.pb({{arr[i],i&1},i});
	}
	sort(all(vc));
	st.clear();
	st.insert(2*n);
	st.insert(0);
	long long ans=0;
	FOR(i,0,2*n-2){
		int I=vc[i].S;
		auto it=st.lower_bound(I);
		int R=*it; R--;
		it--;
		int L=*it; L++;
		ans=max(ans,1LL*((R-L+2)/2)*PAL[I]);
		st.insert(I);
	}
	cout<<ans<<'\n';

	return 0;
	}

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