oj.uz

Submission #534640

# Submission time Handle Problem Language Result Execution time Memory
534640 2022-03-08T12:27:22 Z pnm1384 Palindromes (APIO14_palindrome) C++14
0 / 100
 4 ms 460 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);
	freopen("palindrome.in", "r", stdin);
	freopen("palindrome.out", "w", stdout);
	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;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:53:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  freopen("palindrome.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:54:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  freopen("palindrome.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

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

Subtask #5
0 / 27.0

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