oj.uz

Submission #534628

# Submission time Handle Problem Language Result Execution time Memory
534628 2022-03-08T12:13:19 Z pnm1384 Palindromes (APIO14_palindrome) C++14
0 / 100
 631 ms 30308 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e5 + 20, LG = 20;
int Rank[LG][N], b[N], lef[N], ri[N];
int P[N], Pw;
int n;
stack<int> st;
string ss;

bool cmp(int i, int j)
{
	if (Rank[Pw - 1][i] != Rank[Pw - 1][j]) return Rank[Pw - 1][i] < Rank[Pw - 1][j];
	if (max(i, j) + (1 << (Pw - 1)) >= n) return i > j;
	return Rank[Pw - 1][i + (1 << (Pw - 1))] < Rank[Pw - 1][j + (1 << (Pw - 1))];
}

inline void build_suf()
{
	for (int i = 0; i < n; i++)
	{
		P[i] = i;
		Rank[0][i] = ss[i];
	}
	for (Pw = 1; Pw < LG; Pw++)
	{
		sort(P, P + n, cmp);
		Rank[Pw][P[0]] = 1;
		for (int i = 1; i < n; i++) Rank[Pw][P[i]] = Rank[Pw][P[i - 1]] + cmp(P[i - 1], P[i]);
	}
	return;
}

inline int lcp(int x, int y)
{
	int ans = 0;
	for (int i = LG - 1; i > -1 && x < n && y < n; i--)
	{
		if (Rank[i][x] == Rank[i][y])
		{
			ans |= (1 << i);
			x += (1 << i); y += (1 << i);
		}
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> ss;
	n = (int)ss.size();
	build_suf();
	ll ans = n;
	for (int i = 1; i < n; i++) b[i] = lcp(P[i - 1], P[i]);
	for (int i = 1; i < n; i++)
	{
		while (!st.empty())
		{
			if (b[i] <= b[st.top()])
			{
				st.pop();
				continue;
			}
			break;
		}
		if (st.empty()) lef[i] = 0;
		else lef[i] = st.top();
		st.push(i);
	}
	while (!st.empty()) st.pop();
	for (int i = n - 1; i > 0; i--)
	{
		while (!st.empty())
		{
			if (b[i] <= b[st.top()])
			{
				st.pop();
				continue;
			}
			break;
		}
		if (st.empty()) ri[i] = n;
		else ri[i] = st.top();
		st.push(i);
	}
	for (int i = 1; i < n; i++)
	{
		ans = max(ans, 1ll * b[i] * (ri[i] - lef[i]));
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Incorrect 1 ms 448 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 10120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 29668 KB Output is correct
2 Correct 421 ms 29260 KB Output is correct
3 Correct 462 ms 30308 KB Output is correct
4 Correct 408 ms 29700 KB Output is correct
5 Incorrect 631 ms 29112 KB Output isn't correct
6 Halted 0 ms 0 KB -