oj.uz

Submission #335699

# Submission time Handle Problem Language Result Execution time Memory
335699 2020-12-13T17:56:18 Z alishahali1382 Palindromes (APIO14_palindrome) C++14
100 / 100
 659 ms 63476 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19308 KB Output is correct
2 Correct 13 ms 19308 KB Output is correct
3 Correct 13 ms 19308 KB Output is correct
4 Correct 13 ms 19308 KB Output is correct
5 Correct 13 ms 19308 KB Output is correct
6 Correct 13 ms 19308 KB Output is correct
7 Correct 13 ms 19328 KB Output is correct
8 Correct 13 ms 19308 KB Output is correct
9 Correct 15 ms 19308 KB Output is correct
10 Correct 13 ms 19308 KB Output is correct
11 Correct 13 ms 19308 KB Output is correct
12 Correct 13 ms 19308 KB Output is correct
13 Correct 13 ms 19328 KB Output is correct
14 Correct 13 ms 19308 KB Output is correct
15 Correct 13 ms 19308 KB Output is correct
16 Correct 13 ms 19308 KB Output is correct
17 Correct 13 ms 19308 KB Output is correct
18 Correct 14 ms 19308 KB Output is correct
19 Correct 13 ms 19308 KB Output is correct
20 Correct 14 ms 19308 KB Output is correct
21 Correct 13 ms 19328 KB Output is correct
22 Correct 13 ms 19308 KB Output is correct
23 Correct 13 ms 19308 KB Output is correct
24 Correct 13 ms 19308 KB Output is correct
25 Correct 13 ms 19308 KB Output is correct
26 Correct 13 ms 19308 KB Output is correct
27 Correct 13 ms 19308 KB Output is correct
28 Correct 13 ms 19328 KB Output is correct
29 Correct 13 ms 19320 KB Output is correct
30 Correct 13 ms 19308 KB Output is correct
31 Correct 14 ms 19308 KB Output is correct
32 Correct 13 ms 19308 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19436 KB Output is correct
2 Correct 14 ms 19436 KB Output is correct
3 Correct 15 ms 19436 KB Output is correct
4 Correct 14 ms 19436 KB Output is correct
5 Correct 13 ms 19436 KB Output is correct
6 Correct 15 ms 19436 KB Output is correct
7 Correct 15 ms 19436 KB Output is correct
8 Correct 14 ms 19436 KB Output is correct
9 Correct 14 ms 19564 KB Output is correct
10 Correct 14 ms 19436 KB Output is correct
11 Correct 14 ms 19436 KB Output is correct
12 Correct 14 ms 19436 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 20716 KB Output is correct
2 Correct 22 ms 20716 KB Output is correct
3 Correct 21 ms 20844 KB Output is correct
4 Correct 20 ms 20844 KB Output is correct
5 Correct 22 ms 20844 KB Output is correct
6 Correct 25 ms 20716 KB Output is correct
7 Correct 24 ms 20716 KB Output is correct
8 Correct 23 ms 20844 KB Output is correct
9 Correct 23 ms 20844 KB Output is correct
10 Correct 24 ms 20844 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 33516 KB Output is correct
2 Correct 92 ms 33520 KB Output is correct
3 Correct 90 ms 33900 KB Output is correct
4 Correct 95 ms 33852 KB Output is correct
5 Correct 137 ms 33516 KB Output is correct
6 Correct 135 ms 33588 KB Output is correct
7 Correct 118 ms 33772 KB Output is correct
8 Correct 168 ms 33900 KB Output is correct
9 Correct 158 ms 33900 KB Output is correct
10 Correct 160 ms 34028 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 61836 KB Output is correct
2 Correct 259 ms 61812 KB Output is correct
3 Correct 268 ms 62964 KB Output is correct
4 Correct 252 ms 63220 KB Output is correct
5 Correct 521 ms 61864 KB Output is correct
6 Correct 316 ms 62196 KB Output is correct
7 Correct 338 ms 62324 KB Output is correct
8 Correct 648 ms 63092 KB Output is correct
9 Correct 659 ms 63476 KB Output is correct
10 Correct 574 ms 63368 KB Output is correct
11 Correct 285 ms 61940 KB Output is correct
12 Correct 621 ms 63420 KB Output is correct