oj.uz

Submission #106284

# Submission time Handle Problem Language Result Execution time Memory
106284 2019-04-17T19:02:29 Z Saboon Palindromes (APIO14_palindrome) C++14
23 / 100
 1000 ms 89184 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 3e5 + 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][maxn], lcp[20][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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 75492 KB Output is correct
2 Correct 68 ms 75516 KB Output is correct
3 Correct 71 ms 75516 KB Output is correct
4 Correct 68 ms 75512 KB Output is correct
5 Correct 73 ms 75532 KB Output is correct
6 Correct 68 ms 75512 KB Output is correct
7 Correct 66 ms 75516 KB Output is correct
8 Correct 67 ms 75468 KB Output is correct
9 Correct 72 ms 75512 KB Output is correct
10 Correct 65 ms 75512 KB Output is correct
11 Correct 67 ms 75512 KB Output is correct
12 Correct 71 ms 75512 KB Output is correct
13 Correct 65 ms 75512 KB Output is correct
14 Correct 65 ms 75512 KB Output is correct
15 Correct 71 ms 75640 KB Output is correct
16 Correct 69 ms 75516 KB Output is correct
17 Correct 69 ms 75512 KB Output is correct
18 Correct 69 ms 75512 KB Output is correct
19 Correct 67 ms 75512 KB Output is correct
20 Correct 67 ms 75512 KB Output is correct
21 Correct 70 ms 75548 KB Output is correct
22 Correct 67 ms 75484 KB Output is correct
23 Correct 67 ms 75688 KB Output is correct
24 Correct 73 ms 75464 KB Output is correct
25 Correct 67 ms 75512 KB Output is correct
26 Correct 65 ms 75512 KB Output is correct
27 Correct 66 ms 75528 KB Output is correct
28 Correct 65 ms 75484 KB Output is correct
29 Correct 68 ms 75512 KB Output is correct
30 Correct 69 ms 75640 KB Output is correct
31 Correct 66 ms 75512 KB Output is correct
32 Correct 67 ms 75512 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 75640 KB Output is correct
2 Correct 77 ms 75664 KB Output is correct
3 Correct 98 ms 75640 KB Output is correct
4 Correct 72 ms 75640 KB Output is correct
5 Correct 106 ms 75616 KB Output is correct
6 Correct 100 ms 75640 KB Output is correct
7 Correct 74 ms 75644 KB Output is correct
8 Correct 86 ms 75712 KB Output is correct
9 Correct 69 ms 75640 KB Output is correct
10 Correct 66 ms 75640 KB Output is correct
11 Correct 68 ms 75640 KB Output is correct
12 Correct 69 ms 75640 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 76792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 89184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 36836 KB Time limit exceeded
2 Halted 0 ms 0 KB -