Submission #624356

#	Time	Username	Problem	Language	Result	Execution time	Memory
624356		vovamr	Palindromes (APIO14_palindrome)	C++17	92 / 100	338 ms	26672 KiB

palindrome

#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 (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 (stderr)

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: 0 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27