Submission #527867

#	Time	Username	Problem	Language	Result	Execution time	Memory
527867		pooyashams	Palindromes (APIO14_palindrome)	C++14	0 / 100	705 ms	30536 KiB

palindrome

#pragma GCC diagnostic ignored "-Wmisleading-indentation" // fuck you
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 6e5+10;
const int lgmx = 20;

int rnk[lgmx][maxn];
int P[maxn];
char s[maxn];
int f, pw;

int sfa[maxn];
int lcpa[maxn];
int L[maxn];
int R[maxn];

int n;

inline bool cmp(int i, int j)
{
	return rnk[f-1][i] < rnk[f-1][j] or (rnk[f-1][i] == rnk[f-1][j] and rnk[f-1][i+pw] < rnk[f-1][j+pw]);
}

inline void suffix_array()
{
	iota(P, P+n, 0);
	sort(P, P+n, [&](int i, int j){return s[i] < s[j];});
	rnk[0][P[0]] = 1;
	for(int i = 1; i < n; i++)
		rnk[0][P[i]] = rnk[0][P[i-1]] + (s[P[i]] != s[P[i-1]]);
	pw = 1;
	for(f = 1; f < lgmx; f++)
	{
		sort(P, P+n, cmp);
		rnk[f][P[0]] = 1;
		for(int i = 1; i < n; i++)
			rnk[f][P[i]] = rnk[f][P[i-1]] + cmp(P[i-1], P[i]);
		pw *= 2;
	}
}

inline int lcp(int i, int j)
{
	if(i == j) return n-i;
	int m = 0;
	for(int k = lgmx-1; k >= 0; k--)
	{
		if(rnk[k][i+m] == rnk[k][j+m])
			m += (1<<k);
	}
	return m;
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> s;
	n = strlen(s);
	suffix_array();
	ll ans = n;
	iota(sfa, sfa+n, 0);
	sort(sfa, sfa+n, [&](int i, int j){return rnk[lgmx-1][i] < rnk[lgmx-1][j];});
	for(int i = 1; i < n; i++)
		lcpa[i] = lcp(sfa[i-1], sfa[i]);
	lcpa[0] = -1;
	lcpa[n] = -1;
	L[0] = 0;
	R[n] = n;
	for(int i = 1; i < n; i++) for(L[i] = i-1; lcpa[L[i]] >= lcpa[i]; L[i] = L[L[i]]);
	for(int i = n-1; i >= 0; i--) for(R[i] = i+1; lcpa[R[i]] > lcpa[i]; R[i] = R[R[i]]);
	for(int i = 1; i < n; i++)
		ans = max(ans, 1ll*(R[i]-L[i])*lcpa[i]);
	cout << ans << endl;
	return 0;
}

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