oj.uz

Submission #106298

# Submission time Handle Problem Language Result Execution time Memory
106298 2019-04-17T19:46:57 Z Saboon Palindromes (APIO14_palindrome) C++14
73 / 100
 923 ms 61204 KB 
#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

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 38 ms 41080 KB Output is correct
2 Correct 37 ms 41088 KB Output is correct
3 Correct 36 ms 41080 KB Output is correct
4 Correct 36 ms 41080 KB Output is correct
5 Correct 38 ms 41088 KB Output is correct
6 Correct 36 ms 41076 KB Output is correct
7 Correct 37 ms 41052 KB Output is correct
8 Correct 37 ms 41080 KB Output is correct
9 Correct 40 ms 41088 KB Output is correct
10 Correct 38 ms 41080 KB Output is correct
11 Correct 37 ms 41088 KB Output is correct
12 Correct 38 ms 41080 KB Output is correct
13 Correct 37 ms 41080 KB Output is correct
14 Correct 36 ms 41080 KB Output is correct
15 Correct 36 ms 41080 KB Output is correct
16 Correct 37 ms 41016 KB Output is correct
17 Correct 65 ms 41108 KB Output is correct
18 Correct 37 ms 41080 KB Output is correct
19 Correct 35 ms 41080 KB Output is correct
20 Correct 39 ms 41012 KB Output is correct
21 Correct 38 ms 41084 KB Output is correct
22 Correct 36 ms 41112 KB Output is correct
23 Correct 42 ms 41076 KB Output is correct
24 Correct 41 ms 41080 KB Output is correct
25 Correct 39 ms 41080 KB Output is correct
26 Correct 38 ms 41080 KB Output is correct
27 Correct 39 ms 41148 KB Output is correct
28 Correct 36 ms 41088 KB Output is correct
29 Correct 38 ms 41128 KB Output is correct
30 Correct 38 ms 41088 KB Output is correct
31 Correct 37 ms 41040 KB Output is correct
32 Correct 37 ms 41096 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 41208 KB Output is correct
2 Correct 37 ms 41208 KB Output is correct
3 Correct 40 ms 41208 KB Output is correct
4 Correct 39 ms 41208 KB Output is correct
5 Correct 39 ms 41208 KB Output is correct
6 Correct 43 ms 41208 KB Output is correct
7 Correct 42 ms 41080 KB Output is correct
8 Correct 39 ms 41224 KB Output is correct
9 Correct 38 ms 41208 KB Output is correct
10 Correct 37 ms 41208 KB Output is correct
11 Correct 38 ms 41180 KB Output is correct
12 Correct 37 ms 41208 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 42488 KB Output is correct
2 Correct 63 ms 42360 KB Output is correct
3 Correct 88 ms 43000 KB Output is correct
4 Correct 77 ms 43064 KB Output is correct
5 Correct 75 ms 41848 KB Output is correct
6 Correct 70 ms 42104 KB Output is correct
7 Correct 64 ms 42360 KB Output is correct
8 Correct 59 ms 41848 KB Output is correct
9 Correct 62 ms 41848 KB Output is correct
10 Correct 88 ms 41976 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 54616 KB Output is correct
2 Correct 510 ms 55188 KB Output is correct
3 Correct 600 ms 60460 KB Output is correct
4 Correct 525 ms 61204 KB Output is correct
5 Correct 890 ms 49400 KB Output is correct
6 Correct 780 ms 50836 KB Output is correct
7 Correct 630 ms 55496 KB Output is correct
8 Correct 593 ms 48648 KB Output is correct
9 Correct 734 ms 51604 KB Output is correct
10 Correct 923 ms 50228 KB Output is correct

Subtask #5
0 / 27.0

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