oj.uz

Submission #624358

# Submission time Handle Problem Language Result Execution time Memory
624358 2022-08-08T03:29:46 Z vovamr Palindromes (APIO14_palindrome) C++17
100 / 100
 344 ms 26604 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 3e5 + 100; int m = 300;
int p[N], p2[N], c[N], c2[N], lcp[N], cnt[N];

struct seg_tree {
	int ms;
	int t[4 * N];
	inline void build(int v, int vl, int vr, const ve<int> &a) {
		if (vl == vr) return void(t[v] = a[vl]);
		int m = vl + vr >> 1;
		build(2 * v + 1, vl, m, a);
		build(2 * v + 2, m + 1, vr, a);
		t[v] = min(t[2 * v + 1], t[2 * v + 2]);
	}
	seg_tree(const ve<int> &a) : ms(sz(a)) {
		build(0, 0, ms - 1, a);
	}
	inline int get(int v, int vl, int vr, int pf, int x) {
		if (pf < vl || t[v] > x) return -1;
		else if (vl == vr) return vl;
		int m = vl + vr >> 1;
		if (pf <= m) return get(2 * v + 1, vl, m, pf, x);
		int a = get(2 * v + 2, m + 1, vr, pf, x);
		if (~a) return a;
		return get(2 * v + 1, vl, m, pf, x);
	}
	inline int get(int l, int r, int x) {
		int p = get(0, 0, ms - 1, r, x);
		if (p >= l) return p;
		return -1;
	}
};

inline void solve() {
	string s; cin >> s;
	s += '$'; int n = sz(s);
	for (auto &x : s) ++cnt[x];
	for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
	for (int i = n - 1; ~i; --i) p[--cnt[s[i]]] = i;
	for (int i = 1; i < n; ++i) c[p[i]] = c[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);
	for (int l = 1; l < n; l <<= 1) {
		memset(cnt, 0, sizeof(cnt));
		for (int i = 0; i < n; ++i) { p[i] -= l; if (p[i] < 0){p[i]+=n;} }
		for (int i = 0; i < n; ++i) ++cnt[c[i]];
		for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
		for (int i = n - 1; ~i; --i) p2[--cnt[c[p[i]]]] = p[i];
		memcpy(p, p2, 4 * n); m = 1, c2[p[0]] = 0; pii cur = mpp(c[p[0]], c[(p[0] + l) % n]);
		for (int i = 1; i < n; ++i) {
			pii ce = mpp(c[p[i]], c[(p[i] + l) % n]);
			m += ce != cur, swap(ce, cur); c2[p[i]] = m - 1;
		} memcpy(c, c2, 4 * n);
		if (m == n) break;
	}
	for (int i = 0, k = 0; i < n - 1; ++i) {
		int j = p[c[i] - 1];
		while (s[i + k] == s[j + k]) ++k;
		lcp[c[i]] = k; if (k) --k;
	}

	ve<int> d1(n), d2(n);
	for (int i = 0, l = 0, r = -1; i < n; ++i) {
		int k = (i > r ? 1 : min(r - i + 1, d1[l + r - i]));
		while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) ++k;
		d1[i] = k--; if (i + k > r) l = i - k, r = i + k;
	}
	for (int i = 0, l = 0, r = -1; i < n; ++i) {
		int k = (i > r ? 0 : min(r - i + 1, d2[l + r - i + 1]));
		while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) ++k;
		d2[i] = k--; if (i + k > r) l = i - k - 1, r = i + k;
	}

	ve<int> A(n), B(n);
	for (int i = 0; i < n; ++i) {
		A[i] = i - d1[i] + 1;
		B[i] = i - d2[i];
	}

	seg_tree s1(A);
	seg_tree s2(B);

	auto find_odd = [&](int pos, int len) {
		// p s.t. p - d1[p] + 1 <= pos
		// (p - pos + 1) * 2 - 1 <= len
		// p - pos + 1 <= (len + 1) / 2
		// p <= pos - 1 + ((len + 1) / 2, p >= pos

//		int ans = 0;
//		for (int p = pos; p < n; ++p) {
//			if (p <= pos - 1 + ((len + 1) / 2) && A[p] <= pos) {
//				ans = (p - pos + 1) * 2 - 1;
//			}
//		} return ans;

		int l = pos;
		int r = pos - 1 + (len + 1) / 2;
		int p = s1.get(l, min(n - 1, r), pos);

		if (!~p) return 0;
		return (p - pos + 1) * 2 - 1;
	};
	auto find_even = [&](int pos, int len) {
		// p s.t. p - d2[p] <= pos
		// (p - pos) * 2 <= len
		// p <= pos + (len / 2), p >= pos

//		int ans = 0;
//		for (int p = pos + 1; p < n; ++p) {
//			if (p <= pos + (len / 2) && B[p] <= pos) {
//				ans = (p - pos) * 2;
//			}
//		} return ans;

		int l = pos + 1;
		int r = pos + len / 2;
		int p = s2.get(l, min(n - 1, r), pos);

		if (!~p) return 0;
		return (p - pos) * 2;
	};

	ve<int> stk;
	ve<int> l(n), r(n);

	stk = {0}; l[0] = 0;
	for (int i = 1; i < n; ++i) {
		while (sz(stk) && lcp[stk.back()] >= lcp[i]) stk.pop_back();
		l[i] = sz(stk) ? stk.back() : 0;
		stk.pb(i);
	}
	stk = {n - 1}; r[n - 1] = n - 1;
	for (int i = n - 2; ~i; --i) {
		while (sz(stk) && lcp[stk.back()] >= lcp[i]) stk.pop_back();
		r[i] = sz(stk) ? stk.back() - 1 : n - 1;
		stk.pb(i);
	}

	ll ans = 0;

//	for (int i = 0; i < n; ++i) {
//		cout << p[i] << " " << s.substr(p[i], n - p[i]) << " " << lcp[i] << '\n';
//	}
//	for (int i = 0; i < n; ++i) cout << d1[i] << " ";
//	cout << '\n';
//	for (int i = 0; i < n; ++i) cout << d2[i] << " ";
//	cout << '\n';
//	for (int i = 0; i < n; ++i) {
//		cout << l[i] + 1 << ", " << r[i] + 1 << '\n';
//	}
//	for (int i = 0; i < n; ++i) cout << A[i] + 1 << " ";
//	cout << '\n';
//	for (int i = 0; i < n; ++i) cout << B[i] + 1 << " ";
//	cout << '\n';
//	for (int i = 0; i < n; ++i) {
//		cout << i + 1 << ":" << '\n';
//		cout << "odd: " << find_odd(i, n) << '\n';
//		cout << "even: " << find_even(i, n) << '\n';
//		cout << '\n';
//	}
//	cout << '\n';

	for (int i = 0; i < n; ++i) {
		int pos = p[i];
		int mx = lcp[i];
		int len = max(find_odd(pos, mx), find_even(pos, mx));
		chmax(ans, len * 1ll * (r[i] - l[i] + 1));
	}
	for (int i = 0; i < n; ++i) {
		chmax(ans, 1ll * max(find_odd(i, n), find_even(i, n)));
	}

	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

palindrome.cpp: In member function 'void seg_tree::build(int, int, int, const std::vector<int>&)':
palindrome.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   int m = vl + vr >> 1;
      |           ~~~^~~~
palindrome.cpp: In member function 'int seg_tree::get(int, int, int, int, int)':
palindrome.cpp:42:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int m = vl + vr >> 1;
      |           ~~~^~~~
palindrome.cpp: In function 'void solve()':
palindrome.cpp:58:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |  for (auto &x : s) ++cnt[x];
      |                          ^
palindrome.cpp:60:43: warning: array subscript has type 'char' [-Wchar-subscripts]
   60 |  for (int i = n - 1; ~i; --i) p[--cnt[s[i]]] = i;
      |                                           ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10836 KB Output is correct
2 Correct 5 ms 10880 KB Output is correct
3 Correct 5 ms 10836 KB Output is correct
4 Correct 5 ms 10876 KB Output is correct
5 Correct 5 ms 10836 KB Output is correct
6 Correct 5 ms 10904 KB Output is correct
7 Correct 5 ms 10880 KB Output is correct
8 Correct 5 ms 10836 KB Output is correct
9 Correct 5 ms 10880 KB Output is correct
10 Correct 5 ms 10836 KB Output is correct
11 Correct 5 ms 10836 KB Output is correct
12 Correct 5 ms 10836 KB Output is correct
13 Correct 5 ms 10836 KB Output is correct
14 Correct 5 ms 10836 KB Output is correct
15 Correct 5 ms 10880 KB Output is correct
16 Correct 5 ms 10880 KB Output is correct
17 Correct 5 ms 10836 KB Output is correct
18 Correct 5 ms 10836 KB Output is correct
19 Correct 5 ms 10872 KB Output is correct
20 Correct 6 ms 10836 KB Output is correct
21 Correct 5 ms 10884 KB Output is correct
22 Correct 5 ms 10836 KB Output is correct
23 Correct 5 ms 10836 KB Output is correct
24 Correct 6 ms 10880 KB Output is correct
25 Correct 6 ms 10808 KB Output is correct
26 Correct 5 ms 10876 KB Output is correct
27 Correct 5 ms 10836 KB Output is correct
28 Correct 5 ms 10836 KB Output is correct
29 Correct 5 ms 10836 KB Output is correct
30 Correct 5 ms 10828 KB Output is correct
31 Correct 5 ms 10876 KB Output is correct
32 Correct 5 ms 10836 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10956 KB Output is correct
2 Correct 7 ms 10964 KB Output is correct
3 Correct 5 ms 10964 KB Output is correct
4 Correct 5 ms 10964 KB Output is correct
5 Correct 6 ms 10964 KB Output is correct
6 Correct 7 ms 10876 KB Output is correct
7 Correct 6 ms 10964 KB Output is correct
8 Correct 7 ms 10964 KB Output is correct
9 Correct 5 ms 10964 KB Output is correct
10 Correct 6 ms 10964 KB Output is correct
11 Correct 6 ms 10968 KB Output is correct
12 Correct 7 ms 10968 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11352 KB Output is correct
2 Correct 11 ms 11396 KB Output is correct
3 Correct 10 ms 11480 KB Output is correct
4 Correct 10 ms 11480 KB Output is correct
5 Correct 11 ms 11276 KB Output is correct
6 Correct 11 ms 11352 KB Output is correct
7 Correct 11 ms 11352 KB Output is correct
8 Correct 10 ms 11292 KB Output is correct
9 Correct 10 ms 11352 KB Output is correct
10 Correct 11 ms 11352 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 15824 KB Output is correct
2 Correct 72 ms 15628 KB Output is correct
3 Correct 68 ms 16096 KB Output is correct
4 Correct 70 ms 15936 KB Output is correct
5 Correct 84 ms 15492 KB Output is correct
6 Correct 78 ms 15488 KB Output is correct
7 Correct 70 ms 15692 KB Output is correct
8 Correct 66 ms 15504 KB Output is correct
9 Correct 96 ms 15636 KB Output is correct
10 Correct 87 ms 15572 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 25680 KB Output is correct
2 Correct 212 ms 24844 KB Output is correct
3 Correct 217 ms 26604 KB Output is correct
4 Correct 204 ms 25136 KB Output is correct
5 Correct 282 ms 24500 KB Output is correct
6 Correct 227 ms 25092 KB Output is correct
7 Correct 220 ms 24912 KB Output is correct
8 Correct 229 ms 24608 KB Output is correct
9 Correct 200 ms 24404 KB Output is correct
10 Correct 291 ms 24536 KB Output is correct
11 Correct 260 ms 24840 KB Output is correct
12 Correct 344 ms 24640 KB Output is correct