제출 #624356

#제출 시각아이디문제언어결과실행 시간메모리
624356vovamr회문 (APIO14_palindrome)C++17
92 / 100
338 ms26672 KiB
#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; }

컴파일 시 표준 에러 (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;
      |                                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...