oj.uz

Submission #532982

# Submission time Handle Problem Language Result Execution time Memory
532982 2022-03-04T09:55:33 Z codr0 Palindromes (APIO14_palindrome) C++14
100 / 100
 871 ms 53828 KB 
// 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,2*N-1) fen[i]=0;
		S=0;
	}
	int BSR(int X,int val=-1){
		if(val==-1) 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=-1){
		if(val==-1) 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;
			else 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;
			else 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;
		}
	}
	int L[2*n]={};
	int R[2*n]={};
	vector<pii> vc;
	FOR(i,1,2*n-1){
		while(!vc.empty()&&vc.back().F>=arr[i]){
			L[i]+=(1+L[vc.back().S]);
			vc.pop_back();
		}
		vc.pb({arr[i],i});
	}
	vc.clear();
	FORR(i,2*n-1,1){
		while(!vc.empty()&&vc.back().F>=arr[i]){
			R[i]+=(1+R[vc.back().S]);
			vc.pop_back();
		}
		vc.pb({arr[i],i});
	}
	long long ans=0;
	FOR(i,1,2*n-1) ans=max(ans,1LL*((R[i]+L[i]+1+1)/2)*PAL[i]);
	cout<<ans<<'\n';

	return 0;
	}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2780 KB Output is correct
2 Correct 82 ms 2780 KB Output is correct
3 Correct 74 ms 2680 KB Output is correct
4 Correct 76 ms 2764 KB Output is correct
5 Correct 80 ms 2796 KB Output is correct
6 Correct 76 ms 2772 KB Output is correct
7 Correct 75 ms 2692 KB Output is correct
8 Correct 76 ms 2684 KB Output is correct
9 Correct 78 ms 2704 KB Output is correct
10 Correct 77 ms 2784 KB Output is correct
11 Correct 80 ms 2692 KB Output is correct
12 Correct 75 ms 2680 KB Output is correct
13 Correct 78 ms 2804 KB Output is correct
14 Correct 76 ms 2772 KB Output is correct
15 Correct 82 ms 2768 KB Output is correct
16 Correct 77 ms 2804 KB Output is correct
17 Correct 80 ms 2844 KB Output is correct
18 Correct 77 ms 2676 KB Output is correct
19 Correct 75 ms 2820 KB Output is correct
20 Correct 77 ms 2716 KB Output is correct
21 Correct 80 ms 2740 KB Output is correct
22 Correct 76 ms 2752 KB Output is correct
23 Correct 76 ms 2780 KB Output is correct
24 Correct 78 ms 2760 KB Output is correct
25 Correct 77 ms 2748 KB Output is correct
26 Correct 76 ms 2760 KB Output is correct
27 Correct 77 ms 2808 KB Output is correct
28 Correct 77 ms 2824 KB Output is correct
29 Correct 75 ms 2756 KB Output is correct
30 Correct 75 ms 2756 KB Output is correct
31 Correct 80 ms 2752 KB Output is correct
32 Correct 78 ms 2760 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 2860 KB Output is correct
2 Correct 80 ms 2940 KB Output is correct
3 Correct 77 ms 2856 KB Output is correct
4 Correct 81 ms 2844 KB Output is correct
5 Correct 79 ms 2832 KB Output is correct
6 Correct 80 ms 2932 KB Output is correct
7 Correct 76 ms 2836 KB Output is correct
8 Correct 81 ms 2916 KB Output is correct
9 Correct 79 ms 2856 KB Output is correct
10 Correct 78 ms 2820 KB Output is correct
11 Correct 79 ms 2816 KB Output is correct
12 Correct 76 ms 2836 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 4320 KB Output is correct
2 Correct 96 ms 4328 KB Output is correct
3 Correct 89 ms 4492 KB Output is correct
4 Correct 91 ms 4440 KB Output is correct
5 Correct 92 ms 4184 KB Output is correct
6 Correct 90 ms 4176 KB Output is correct
7 Correct 92 ms 4216 KB Output is correct
8 Correct 92 ms 4148 KB Output is correct
9 Correct 89 ms 4192 KB Output is correct
10 Correct 90 ms 4164 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 18424 KB Output is correct
2 Correct 253 ms 18076 KB Output is correct
3 Correct 233 ms 19184 KB Output is correct
4 Correct 245 ms 18728 KB Output is correct
5 Correct 269 ms 17412 KB Output is correct
6 Correct 268 ms 17616 KB Output is correct
7 Correct 262 ms 18088 KB Output is correct
8 Correct 293 ms 17316 KB Output is correct
9 Correct 302 ms 17828 KB Output is correct
10 Correct 289 ms 17252 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 50236 KB Output is correct
2 Correct 656 ms 47872 KB Output is correct
3 Correct 577 ms 53828 KB Output is correct
4 Correct 622 ms 49564 KB Output is correct
5 Correct 766 ms 46884 KB Output is correct
6 Correct 682 ms 48656 KB Output is correct
7 Correct 682 ms 48124 KB Output is correct
8 Correct 871 ms 46424 KB Output is correct
9 Correct 853 ms 46720 KB Output is correct
10 Correct 801 ms 46776 KB Output is correct
11 Correct 651 ms 47900 KB Output is correct
12 Correct 851 ms 47280 KB Output is correct