Submission #624356

# Submission time Handle Problem Language Result Execution time Memory
624356 2022-08-08T03:27:54 Z vovamr Palindromes (APIO14_palindrome) C++17
92 / 100
338 ms 26672 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 (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;
      |                                           ^
# Verdict Execution time Memory Grader output
1 Correct 5 ms 10836 KB Output is correct
2 Correct 5 ms 10836 KB Output is correct
3 Correct 5 ms 10876 KB Output is correct
4 Incorrect 5 ms 10836 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 10876 KB Output is correct
2 Correct 5 ms 10864 KB Output is correct
3 Correct 6 ms 10964 KB Output is correct
4 Correct 5 ms 10876 KB Output is correct
5 Correct 6 ms 10884 KB Output is correct
6 Correct 6 ms 10964 KB Output is correct
7 Correct 5 ms 10964 KB Output is correct
8 Correct 7 ms 10964 KB Output is correct
9 Correct 6 ms 10964 KB Output is correct
10 Correct 5 ms 10872 KB Output is correct
11 Correct 5 ms 10964 KB Output is correct
12 Correct 6 ms 10964 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 11 ms 11348 KB Output is correct
2 Correct 12 ms 11348 KB Output is correct
3 Correct 11 ms 11396 KB Output is correct
4 Correct 11 ms 11476 KB Output is correct
5 Correct 12 ms 11424 KB Output is correct
6 Correct 11 ms 11408 KB Output is correct
7 Correct 11 ms 11300 KB Output is correct
8 Correct 10 ms 11272 KB Output is correct
9 Correct 11 ms 11348 KB Output is correct
10 Correct 10 ms 11380 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 69 ms 15872 KB Output is correct
2 Correct 69 ms 15616 KB Output is correct
3 Correct 69 ms 16160 KB Output is correct
4 Correct 66 ms 15872 KB Output is correct
5 Correct 84 ms 15552 KB Output is correct
6 Correct 74 ms 15484 KB Output is correct
7 Correct 73 ms 15700 KB Output is correct
8 Correct 63 ms 15608 KB Output is correct
9 Correct 96 ms 15692 KB Output is correct
10 Correct 86 ms 15496 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 222 ms 25680 KB Output is correct
2 Correct 212 ms 24788 KB Output is correct
3 Correct 211 ms 26672 KB Output is correct
4 Correct 204 ms 25144 KB Output is correct
5 Correct 254 ms 24532 KB Output is correct
6 Correct 225 ms 25160 KB Output is correct
7 Correct 241 ms 24800 KB Output is correct
8 Correct 199 ms 24524 KB Output is correct
9 Correct 223 ms 24432 KB Output is correct
10 Correct 286 ms 24520 KB Output is correct
11 Correct 233 ms 24740 KB Output is correct
12 Correct 338 ms 24624 KB Output is correct