Submission #534030

#	Time	Username	Problem	Language	Result	Execution time	Memory
534030		getac	Palindromes (APIO14_palindrome)	C++14	0 / 100	817 ms	36484 KiB

palindrome

//InTheNameOfGOD
//PRS;)
#include<iostream>
#include<algorithm>
#include<vector>
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pl;
typedef pair<int, pl> pi;
typedef long long ll;
const int xn = 3e5 + 5;
int r[xn << 1][20];
pi a[xn];
pl b[xn];
inline int lcp(int x, int y)
{
	int t = 0;
	for(int i = 18; i >= 0; i--) if(r[x + t][i] == r[y + t][i]) t += (1 << i);
	return t;
}
int main()
{
	Fast
	string s;
	cin >> s;
	int n = s.size();
	for(int i = 0; i < n; i++) r[i][0] = s[i] - 'a' + 1;
	for(int j = 1; j < 20; j++)
	{
		int j1 = j - 1;
		for(int i = 0; i < n; i++) a[i] = {r[i][j1], {r[i + (1 << j1)][j1], i}};
		sort(a, a + n);
		r[a[0].Y.Y][j] = 1;
		for(int i = 1; i < n; i++)
		{
			r[a[i].Y.Y][j] = r[a[i - 1].Y.Y][j];
			if(a[i - 1].X < a[i].X || a[i - 1].Y.X < a[i].Y.X) r[a[i].Y.Y][j]++;
		}
	}
	for(int i = 0; i < n; i++) b[i] = {r[i][19], i};
	sort(b, b + n);
	vector<pi> v;
	ll ans = n;
	for(int i = 1; i < n; i++)
	{
		int e = lcp(b[i - 1].Y, b[i].Y), prs = 0;
		while(!v.empty() && v.back().X >= e)
		{
			pi p = v.back();
			v.pop_back();
			if(p.X == e) continue;
			ans = max(ans, 1ll * (i - p.Y.X) * p.X);
		}
		if(!v.empty()) prs = v.back().Y.Y;
		v.push_back({e, {prs, i}});
	}
	for(pi p : v) ans = max(ans, 1ll * (n - p.Y.X) * p.X);
	return cout << ans << '\n', 0;
}

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