Submission #532940

#	Time	Username	Problem	Language	Result	Execution time	Memory
532940		codr0	Palindromes (APIO14_palindrome)	C++14	73 / 100	856 ms	56748 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 BASE=131;
const int MOD=998765431;
const int N=3e5+1e4;
struct fenwick{
	int fen[2*N],S,pw[20];
	fenwick(){
		pw[0]=1;
		FOR(i,1,19) pw[i]=pw[i-1]*2;
	}
	void insert(int k){
		if(!k){
			S++;
			return;
		}
		while(k<2*N){
			fen[k]++;
			k+=(k&(-k));
		}
	}
	int get(int k){
		int rt=S;
		while(k>0){
			rt+=fen[k];
			k-=(k&(-k));
		}
		return rt;
	}
	void clear(){
		FOR(i,0,N-1) fen[i]=0;
		S=0;
	}
	int BSR(int X){
		int val=get(X);
		int ind=0;
		int sum=S;
		FORR(j,19,0) if(ind+pw[j]<2*N&&sum+fen[ind+pw[j]]<=val){
			sum+=fen[ind+pw[j]];
			ind+=pw[j];
		}
		return (ind+1);
	}
	int BSL(int X){
		int val=get(X)-1;
		if(val==S-1) return 0;
		int ind=0;
		int sum=S;
		FORR(j,19,0) if(ind+pw[j]<2*N&&sum+fen[ind+pw[j]]<=val){
			sum+=fen[ind+pw[j]];
			ind+=pw[j];
		}
		return (ind+1);
	}
};fenwick fen;
string s;
int n;
int arr[2*N];
int hshR[N],hsh[N];
int PAL[2*N];
int pw[N],inv[N];

vector<int> suffix_array(string S){
  S.push_back(0);
  int N = S.size();
  vector<int> cnt(128, 0);
  for (int i = 0; i < N; i++){
    cnt[S[i]]++;
  }
  for (int i = 0; i < 127; i++){
    cnt[i + 1] += cnt[i];
  }
  vector<int> SA(N);
  for (int i = 0; i < N; i++){
    cnt[S[i]]--;
    SA[cnt[S[i]]] = i;
  }
  vector<int> rank(N);
  rank[SA[0]] = 0;
  for (int i = 0; i < N - 1; i++){
    rank[SA[i + 1]] = rank[SA[i]];
    if (S[SA[i]] != S[SA[i + 1]]){
      rank[SA[i + 1]]++;
    }
  }
  int L = 1;
  while (L < N){
    vector<int> SA2(N);
    for (int i = 0; i < N; i++){
      SA2[i] = SA[i] - L;
      if (SA2[i] < 0){
        SA2[i] += N;
      }
    }
    cnt = vector<int>(N, 0);
    for (int i = 0; i < N; i++){
      cnt[rank[SA2[i]]]++;
    }
    for (int i = 0; i < N - 1; i++){
      cnt[i + 1] += cnt[i];
    }
    for (int i = N - 1; i >= 0; i--){
      cnt[rank[SA2[i]]]--;
      SA[cnt[rank[SA2[i]]]] = SA2[i];
    }
    vector<int> rank2(N);
    rank2[SA[0]] = 0;
    for (int i = 0; i < N - 1; i++){
      rank2[SA[i + 1]] = rank2[SA[i]];
      if (rank[SA[i]] != rank[SA[i + 1]] || rank[(SA[i] + L) % N] != rank[(SA[i + 1] + L) % N]){
        rank2[SA[i + 1]]++;
      }
    }
    rank = rank2;
    L *= 2;
  }
  SA.erase(SA.begin());
  return SA;
}

	inline int mul(int a,int b){
		int rt=(1LL*a*b)%MOD;
		return rt;
	}

	inline int mkey(int a,int b){
		int rt=a+b;
		if(rt<0) rt+=MOD;
		if(rt>=MOD) rt-=MOD;
		return rt;
	}

	int HSH(int l,int r){
		int rt=mkey(hsh[r],-hsh[l-1]);
		rt=mul(rt,inv[l-1]);
		return rt;
	}

	int HSHR(int l,int r){
		int rt=mkey(hshR[l],-hshR[r+1]);
		rt=mul(rt,inv[n-r]);
		return rt;
	}

	int PW(int a,int b){
		if(!b) return 1;
		int rt=PW(a,b/2);
		rt=mul(rt,rt);
		if(b&1) rt=mul(rt,a);
		return rt;
	}

	int lcp(int I,int J){
		int l=0,r=n+1;
		while(r-l>1){
			int mid=(r+l)/2;
			if(max(I,J)+mid>(n+1)) r=mid;
			if(HSH(I,I+mid-1)==HSH(J,J+mid-1)) l=mid;
			else r=mid;
		}
		return l;
	}

	int pal(int i,int j){
		int l=0,r=n+1;
		while(r-l>1){
			int mid=(r+l)/2;
			if(i-mid<0||j+mid>(n+1)) r=mid;
			if(HSHR(i-mid+1,i)==HSH(j,j+mid-1)) l=mid;
			else r=mid;
		}
		return l;
	}

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

	pw[0]=1; inv[0]=1; FOR(i,1,N-1) pw[i]=mul(pw[i-1],BASE),inv[i]=PW(pw[i],MOD-2);
	cin>>s; vector<int> X0=suffix_array(s); n=SZ(s);
	s='$'+s;
	hsh[0]=0;
	FOR(i,1,n) hsh[i]=mkey(hsh[i-1],mul((s[i]-'a'+1),pw[i-1]));
	hshR[n+1]=0;
	FORR(i,n,1) hshR[i]=mkey(hshR[i+1],mul((s[i]-'a'+1),pw[n-i]));
	int sa[n+1];
	FOR(i,1,n) sa[i]=X0[i-1]+1;	
	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);
	FOR(j,n+1,2*n-1) for(int x0:ind[j]) fen.insert(x0);
	fen.insert(2*n+1);
	FOR(i,1,n){
		for(int x0:ind[n+1-i]) fen.insert(x0);
		int mid=0;
		mid=(i+n)/2;
		if((i+n)%2==0){
			mid=mid*2-1;
		}else{
			mid=mid*2;
		}
		int it=fen.BSL(mid);
		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=fen.BSL(mid);
			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));
	fen.clear();
	fen.insert(2*n);
	fen.insert(0);
	long long ans=0;
	FOR(i,0,2*n-2){
		int I=vc[i].S;
		int it=fen.BSR(I);
		int R=it; R--;
		it=fen.BSL(I);
		int L=it; L++;
		ans=max(ans,1LL*((R-L+2)/2)*PAL[I]);
		fen.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