Submission #106298

#	Time	Username	Problem	Language	Result	Execution time	Memory
106298		Saboon	Palindromes (APIO14_palindrome)	C++14	73 / 100	923 ms	61204 KiB

palindrome

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 1e5 + 10;

string s;
int n, m;
int pos[2 * maxn], suf[2 * maxn], tmp[2 * maxn], parsum[2 * maxn], LOG[2 * maxn];
int gap;
ll answer = 0;

bool sufCmp(int i, int j){
	if (pos[i] != pos[j])
		return pos[i] < pos[j];
	i += gap, j += gap;
	return (i < m && j < m) ? pos[i] < pos[j] : i > j;
}

void buildSA(){
	m = s.size();
	for (int i = 0; i < m; i++){
		suf[i] = i;
		pos[i] = (int)(s[i] - 'a');
	}
	for (gap = 1; ; gap += gap){
		sort(suf, suf + m, sufCmp);
		for (int j = 1; j < m; j++)
			tmp[j] = tmp[j - 1] + sufCmp(suf[j - 1], suf[j]);
		for (int j = 0; j < m; j++)
			pos[suf[j]] = tmp[j];
		if (tmp[m - 1] == m - 1)
			break;
	}
	for (int i = 0; i < m; i++)
		parsum[i] = (suf[i] < n) + ((i > 0) ? parsum[i - 1] : 0);
}

int rcp[20][2 * maxn], lcp[20][2 * maxn];

void buildLCP(){
	memset(lcp, 63, sizeof lcp);
	memset(rcp, 63, sizeof rcp);
	for (int i = 0, k = 0; i < m; i++){
		if (pos[i] != m - 1){
			for (int j = suf[pos[i] + 1]; s[i + k] == s[j + k];)
				k ++;
			lcp[0][pos[i] + 1] = k;
			rcp[0][pos[i] + 0] = k;
			if (k > 0)
				k --;
		}
	}
	for (int i = 0; i < 19; i++)
		for (int j = 0; j + (1 << i) < m; j++)
			rcp[i + 1][j] = min(rcp[i][j], rcp[i][j + (1 << i)]);
	for (int i = 0; i < 19; i++)
		for (int j = m - 1; j - (1 << i) >= 0; j--)
			lcp[i + 1][j] = min(lcp[i][j], lcp[i][j - (1 << i)]);
}

inline int get_lcp(int i, int j){
	if (i == j)
		return m - i;
	if (i > j)
		swap(i, j);
	int len = LOG[j - i];
	return min(rcp[len][i], lcp[len][j]);
}

vector<int> seg[4 * maxn];

void check(int lef, int rig){
	int L, R;
	int len = rig - lef + 1;
	int idx = pos[lef];
	for (int i = 19; i >= 0; i--)
		if (idx - (1 << i) >= 0 and lcp[i][idx] >= len)
			idx -= (1 << i);
	L = idx;
	idx = pos[lef];
	for (int i = 19; i >= 0; i--)
		if (idx + (1 << i) < m and rcp[i][idx] >= len)
			idx += (1 << i);
	R = idx;
	int num = parsum[R] - (L > 0 ? parsum[L - 1] : 0);
	answer = max(answer, 1ll * num * len);
}

void get(int id, int L, int R, int idx, int len){
	for (int i = 0; i < seg[id].size() and seg[id][i] < 0; i++){
		int t = -seg[id][i] - 1;
		if (2 * (t - idx + 1) <= len)
			break;
		check(idx, idx + 2 * (t - idx + 1) - 1); 
	}
	for (int i = (int)seg[id].size() - 1; i >= 0 and seg[id][i] > 0; i--){
		int t = seg[id][i] - 1;
		if (2 * (t - idx) + 1 <= len)
			break;
		check(idx, idx + 2 * (t - idx));
	}
	if (L + 1 == R)
		return;
	int mid = (L + R) >> 1;
	if (idx < mid)
		get(2 * id + 0, L, mid, idx, len);
	else
		get(2 * id + 1, mid, R, idx, len);
}

void add(int id, int L, int R, int l, int r, int idx){
	if (L == l and R == r){
		seg[id].push_back(idx);
		return;
	}
	int mid = (L + R) >> 1;
	if (l < mid)
		add(2 * id + 0, L, mid, l, min(mid, r), idx);
	if (mid < r)
		add(2 * id + 1, mid, R, max(l, mid), r, idx);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin >> s;
	n = s.size();
	string obj = s + "#";
	reverse(s.begin(), s.end());
	obj += s;
	s = obj;
	buildSA();
	buildLCP();
	for (int i = 1; i <= m; i++)
		LOG[i] = log2(i);
	for (int i = 0; i < n; i++){
		int lo = 0, hi = min(i + 1, n - i);
		while (hi - lo > 1){
			int mid = (lo + hi) >> 1;
			if (get_lcp(pos[i - mid], pos[(1 + n) + (n - i - mid - 1)]) >= mid)
				lo = mid;
			else
				hi = mid;
		}
		add(1, 0, n, i - lo, i + 1, +(i + 1));
		lo = 0, hi = min(i + 2, n - i);
		while (hi - lo > 1){
			int mid = (lo + hi) >> 1;
			if (get_lcp(pos[i - mid + 1], pos[(1 + n) + (n - i - mid - 1)]) >= mid)
				lo = mid;
			else
				hi = mid;
		}
		if (lo > 0)
			add(1, 0, n, i - lo + 1, i + 1, -(i + 1));
	}
	for (int i = 0; i < 4 * maxn; i++)
		sort(seg[i].begin(), seg[i].end());
	int last = -1, len = 0;
	for (int i = 0; i < m; i++){
		if (suf[i] >= n)
			continue;
		if (last != -1)
			len = get_lcp(pos[suf[i]], pos[last]);
		last = suf[i];
		get(1, 0, n, suf[i], len);
	}
	cout << answer << endl;
}

Compilation message (stderr)

palindrome.cpp: In function 'void get(int, int, int, int, int)':
palindrome.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < seg[id].size() and seg[id][i] < 0; i++){
                  ~~^~~~~~~~~~~~~~~~

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