제출 #752922

#제출 시각아이디문제언어결과실행 시간메모리
752922I_love_Hoang_Yen서열 (APIO23_sequence)C++17
7 / 100
308 ms31832 KiB
#include "sequence.h" #include <bits/stdc++.h> #define SZ(s) ((int) ((s).size())) using namespace std; vector<int> medians(const vector<int> values) { int n = SZ(values); assert(n > 0); if (n % 2 == 0) { return {values[n/2 - 1], values[n / 2]}; } else { return {values[n/2]}; } } int sub1(const vector<int>& a) { int n = SZ(a); int res = 0; for (int l = 0; l < n; ++l) { for (int r = l; r < n; ++r) { vector<int> b(a.begin() + l, a.begin() + r + 1); unordered_map<int, int> cnt; for (int val : b) cnt[val] += 1; sort(b.begin(), b.end()); auto meds = medians(b); for (int med : meds) { res = max(res, cnt[med]); } } } return res; } #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; using namespace __gnu_pbds; int sub2(const vector<int>& a) { int n = SZ(a); int res = 0; for (int l = 0; l < n; ++l) { unordered_map<int, int> cnt; ordered_set values; for (int r = l; r < n; ++r) { cnt[a[r]]++; values.insert(a[r]); int k = SZ(values); if (k % 2 == 0) { res = max(res, cnt[*values.find_by_order(k / 2 - 1)]); res = max(res, cnt[*values.find_by_order(k / 2)]); } else { res = max(res, cnt[*values.find_by_order(k / 2)]); } } } return res; } bool is_sub_3(const std::vector<int> a) { auto mit = max_element(a.begin(), a.end()); return std::is_sorted(a.begin(), mit) && std::is_sorted(mit, a.end(), std::greater<int>()); } int len(const std::pair<int,int>& p) { return p.second - p.first + 1; } bool can_be_median(int cnt_less, int cnt_equal, int cnt_greater) { return cnt_equal + cnt_less >= cnt_greater; } int sub3(const vector<int>& a) { int n = SZ(a); unordered_map<int, vector<pair<int,int>>> pos; int l = 0; while (l < n) { int r = l; while (r < n && a[l] == a[r]) ++r; pos[a[l]].emplace_back(l, r-1); l = r; } int res = 0; for (const auto& [val, lrs] : pos) { // only 1 segment for (const auto& lr : lrs) res = max(res, len(lr)); // 2 segments if (SZ(lrs) < 2) continue; assert(SZ(lrs) == 2); int cnt_equal = len(lrs[0]) + len(lrs[1]); int cnt_greater = len({lrs[0].second + 1, lrs[1].first - 1}); int cnt_less = len({0, lrs[0].first - 1}) + len({lrs[1].second + 1, n-1}); if (can_be_median(cnt_less, cnt_equal, cnt_greater)) { res = max(res, cnt_equal); } } return res; } // SegTree, copied from AtCoder library {{{ // AtCoder doc: https://atcoder.github.io/ac-library/master/document_en/segtree.html // // Notes: // - Index of elements from 0 -> n-1 // - Range queries are [l, r-1] // // Tested: // - (binary search) https://atcoder.jp/contests/practice2/tasks/practice2_j // - https://oj.vnoi.info/problem/gss // - https://oj.vnoi.info/problem/nklineup // - (max_right & min_left for delete position queries) https://oj.vnoi.info/problem/segtree_itstr // - https://judge.yosupo.jp/problem/point_add_range_sum // - https://judge.yosupo.jp/problem/point_set_range_composite int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } template< class T, // data type for nodes T (*op) (T, T), // operator to combine 2 nodes T (*e)() // identity element > struct SegTree { SegTree() : SegTree(0) {} explicit SegTree(int n) : SegTree(vector<T> (n, e())) {} explicit SegTree(const vector<T>& v) : _n((int) v.size()) { log = ceil_pow2(_n); size = 1<<log; d = vector<T> (2*size, e()); for (int i = 0; i < _n; i++) d[size+i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } // 0 <= p < n void set(int p, T x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } // 0 <= p < n T get(int p) const { assert(0 <= p && p < _n); return d[p + size]; } // Get product in range [l, r-1] // 0 <= l <= r <= n // For empty segment (l == r) -> return e() T prod(int l, int r) const { assert(0 <= l && l <= r && r <= _n); T sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } T all_prod() const { return d[1]; } // Binary search on SegTree to find largest r: // f(op(a[l] .. a[r-1])) = true (assuming empty array is always true) // f(op(a[l] .. a[r])) = false (assuming op(..., a[n]), which is out of bound, is always false) template <bool (*f)(T)> int max_right(int l) const { return max_right(l, [](T x) { return f(x); }); } template <class F> int max_right(int l, F f) const { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; T sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } // Binary search on SegTree to find smallest l: // f(op(a[l] .. a[r-1])) = true (assuming empty array is always true) // f(op(a[l-1] .. a[r-1])) = false (assuming op(a[-1], ..), which is out of bound, is always false) template <bool (*f)(T)> int min_left(int r) const { return min_left(r, [](T x) { return f(x); }); } template <class F> int min_left(int r, F f) const { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; T sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; vector<T> d; void update(int k) { d[k] = op(d[2*k], d[2*k+1]); } }; // }}} // SegTree examples {{{ // Examples: Commonly used SegTree ops: max / min / sum struct MaxSegTreeOp { static int op(int x, int y) { return max(x, y); } static int e() { return INT_MIN; } }; struct MinSegTreeOp { static int op(int x, int y) { return min(x, y); } static int e() { return INT_MAX; } }; struct SumSegTreeOp { static long long op(long long x, long long y) { return x + y; } static long long e() { return 0; } }; // using STMax = SegTree<int, MaxSegTreeOp::op, MaxSegTreeOp::e>; // using STMin = SegTree<int, MinSegTreeOp::op, MinSegTreeOp::e>; // using STSum = SegTree<int, SumSegTreeOp::op, SumSegTreeOp::e>; // }}} int sub4(const vector<int>& a) { int n = SZ(a); int res = 0; int ln = *max_element(a.begin(), a.end()); for (int median = 0; median <= ln; ++median) { vector<int> cnt_less(n, 0); vector<int> cnt_equal(n, 0); vector<int> cnt_greater(n, 0); // [l, r] satisfies <=> cnt_less(l, r) + cnt_equal(l, r) - cnt_greater(l, r) >= 0 // Fix l => Find max r: // cnt_less(l, r) + cnt_equal(l, r) - cnt_greater(l, r) >= 0 // <=> cnt_less[r] + cnt_equal[r] - cnt_greater[r] // >= cnt_less[l-1] + cnt_equal[l-1] - cnt_greater[l-1] for (int i = 0; i < n; ++i) { cnt_less[i] = a[i] < median; cnt_equal[i] = a[i] == median; cnt_greater[i] = a[i] > median; } std::partial_sum(cnt_less.begin(), cnt_less.end(), cnt_less.begin()); std::partial_sum(cnt_equal.begin(), cnt_equal.end(), cnt_equal.begin()); std::partial_sum(cnt_greater.begin(), cnt_greater.end(), cnt_greater.begin()); // st: stores max(r) SegTree<int, MaxSegTreeOp::op, MaxSegTreeOp::e> st(2 * n + 1); auto f = [&] (int i) { if (i < 0) return n; // +n to make sure result >= 0 return cnt_less[i] + cnt_equal[i] - cnt_greater[i] + n; }; for (int l = n-1; l >= 0; --l) { int r = st.prod(f(l-1), 2*n + 1); if (r >= l) { int equals = cnt_equal[r] - (l > 0 ? cnt_equal[l-1] : 0); res = max(res, equals); } st.set(f(l), max(st.get(f(l)), l)); } } return res; } int sequence(int n, std::vector<int> a) { if (n <= 2000 || *max_element(a.begin(), a.end()) <= 3) return sub4(a); if (is_sub_3(a)) return sub3(a); return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...