Submission #826136

#TimeUsernameProblemLanguageResultExecution timeMemory
826136KoDSequence (APIO23_sequence)C++17
100 / 100
771 ms46632 KiB
#include "sequence.h" #include <algorithm> #include <utility> #include <vector> using std::pair; using std::vector; struct node { int min, max, sum; static node id() { return {0, 0, 0}; } static node one(int x) { return {std::min(x, 0), std::max(x, 0), x}; } node operator+(const node& n) const { return node(*this) += n; } node& operator+=(const node& n) { min = std::min(min, n.min + sum); max = std::max(max, n.max + sum); sum += n.sum; return *this; } }; struct segment_tree { explicit segment_tree(int n, const node& x) : size(n), data(2 * n, x) { for (int i = n - 1; i > 0; --i) fetch(i); } void set(int i, const node& n) { i += size; data[i] = n; while (i >>= 1) fetch(i); } node fold(int l, int r) { l += size, r += size; node ret_l = node::id(), ret_r = node::id(); for (; l < r; l >>= 1, r >>= 1) { if (l & 1) ret_l += data[l++]; if (r & 1) ret_r = data[--r] + ret_r; } return ret_l + ret_r; } private: int size; vector<node> data; void fetch(int i) { data[i] = data[2 * i + 0] + data[2 * i + 1]; } }; int sequence(int N, vector<int> A) { vector<vector<int>> C(N); for (int i = 0; i < N; ++i) { A[i] -= 1; C[A[i]].push_back(i); } int ret = 0; for (int i = 0, j = 0; i < N; ++i) { const int c = (int)C[i].size(); if (j <= N / 2 && N / 2 < j + c) ret = std::max(ret, c); j += c; } for (int phase = 0; phase < 2; ++phase) { segment_tree seg(N, node::one(-1)); for (int x = 0; x < N; ++x) { const auto& v = C[x]; const int n = (int)v.size(); for (int i = 0, j = 0; i < n; ++i) { const auto [l0, r0, $0] = seg.fold(0, v[i]); while (j < n) { const int offset = seg.fold(0, v[j] + 1).sum; const auto [l1, r1, $1] = seg.fold(v[j] + 1, N); if (std::max(l0, l1 + offset) > std::min(r0, r1 + offset)) break; j += 1; } ret = std::max(ret, j - i); } for (const int i : v) seg.set(i, node::one(+1)); } std::reverse(C.begin(), C.end()); } return ret; }
#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...