oj.uz

Submission #106296

# Submission time Handle Problem Language Result Execution time Memory
106296 2019-04-17T19:44:29 Z Saboon Palindromes (APIO14_palindrome) C++14
47 / 100
 1000 ms 132096 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][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

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 107 ms 122488 KB Output is correct
2 Correct 109 ms 122616 KB Output is correct
3 Correct 103 ms 122488 KB Output is correct
4 Correct 106 ms 122528 KB Output is correct
5 Correct 109 ms 122488 KB Output is correct
6 Correct 112 ms 122428 KB Output is correct
7 Correct 104 ms 122436 KB Output is correct
8 Correct 104 ms 122424 KB Output is correct
9 Correct 109 ms 122616 KB Output is correct
10 Correct 105 ms 122428 KB Output is correct
11 Correct 104 ms 122488 KB Output is correct
12 Correct 110 ms 122488 KB Output is correct
13 Correct 106 ms 122456 KB Output is correct
14 Correct 110 ms 122508 KB Output is correct
15 Correct 104 ms 122488 KB Output is correct
16 Correct 106 ms 122488 KB Output is correct
17 Correct 101 ms 122488 KB Output is correct
18 Correct 102 ms 122468 KB Output is correct
19 Correct 100 ms 122588 KB Output is correct
20 Correct 103 ms 122488 KB Output is correct
21 Correct 115 ms 122488 KB Output is correct
22 Correct 110 ms 122488 KB Output is correct
23 Correct 109 ms 122468 KB Output is correct
24 Correct 120 ms 122424 KB Output is correct
25 Correct 107 ms 122452 KB Output is correct
26 Correct 111 ms 122460 KB Output is correct
27 Correct 106 ms 122416 KB Output is correct
28 Correct 103 ms 122556 KB Output is correct
29 Correct 102 ms 122492 KB Output is correct
30 Correct 103 ms 122488 KB Output is correct
31 Correct 109 ms 122488 KB Output is correct
32 Correct 106 ms 122492 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 122616 KB Output is correct
2 Correct 114 ms 122616 KB Output is correct
3 Correct 107 ms 122628 KB Output is correct
4 Correct 109 ms 122676 KB Output is correct
5 Correct 111 ms 122744 KB Output is correct
6 Correct 114 ms 122600 KB Output is correct
7 Correct 108 ms 122616 KB Output is correct
8 Correct 110 ms 122588 KB Output is correct
9 Correct 108 ms 122616 KB Output is correct
10 Correct 111 ms 122492 KB Output is correct
11 Correct 103 ms 122488 KB Output is correct
12 Correct 105 ms 122616 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 123772 KB Output is correct
2 Correct 140 ms 123948 KB Output is correct
3 Correct 149 ms 124332 KB Output is correct
4 Correct 141 ms 124600 KB Output is correct
5 Correct 142 ms 123384 KB Output is correct
6 Correct 137 ms 123512 KB Output is correct
7 Correct 142 ms 124028 KB Output is correct
8 Correct 129 ms 123256 KB Output is correct
9 Correct 126 ms 123340 KB Output is correct
10 Correct 145 ms 123384 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 431 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

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