232-aka-pretty-pi 님의 블로그 232-aka-pretty-pi 님의 블로그

http://boj.kr/a5d6c86649774b01ade9d98b172d36b2update : edges order maintainedtemplate struct CompressedSparseRow { struct Proxy { using citer = typename std::vector::const_iterator; citer first; citer last; [[nodiscard]] citer begin() const { return first; } [[nodiscard]] citer end() const { return last; } }; int n; std::vector cnt; std::vector all; std::vect..

template >struct Rmq { constexpr static int B = 64; using uint64 = unsigned long long; int n; std::vector> mat; std::vector pref; std::vector suff; std::vector a; std::vector avail; Cmp cmp; Rmq(const std::vector& _a, Cmp&& _cmp = Cmp {}) : n(int(_a.size())), pref(_a), suff(_a), a(_a), cmp(_cmp) { for (int i = 1; i = 0; --i) { if (i % B != B - 1) { suff[i] = std::min(suf..

namespace radix { std::array radix_cnt; template void takeStep(std::vector& a, std::vector& new_a, int shift) { std::fill(radix_cnt.begin(), radix_cnt.end(), 0); for (const auto& x : a) { radix_cnt[x >> shift & 0xffff] += 1; } std::partial_sum(radix_cnt.begin(), radix_cnt.end(), radix_cnt.begin()); for (int i = int(a.size()) - 1; i >= 0; --i) { new_a[--radix_cnt[a[i]..

template struct SegmentTree { int n; mutable std::vector a; void pull(int x, int l, int r) { int m = l + (r - l) / 2; a[x] = a[x + 1] + a[x + 2 * (m - l)]; } explicit SegmentTree(int arg_n) : n(arg_n) { assert(n > 0); a.resize(2 * n - 1); auto build = [&](auto&& self, int x, int l, int r) -> void { if (r - l == 1) { return; } int m = l + (r - l) / 2; ..

std::deque는 청크 단위로 메모리를 할당하고, 이로 인해 캐시히트가 떨어지고 덱을 여러 개 선언했을 때 메모리를 엄청나게 많이 잡아 먹는다는 단점이 있다.std::stack과 std::queue는 기본 컨테이너로 std::deque를 사용한다. (https://en.cppreference.com/w/cpp/container/stack) (https://en.cppreference.com/w/cpp/container/queue)따라서 STL의 스택과 큐, 덱은 모두 느리고, 메모리를 많이 먹는다는 단점을 공유한다.실제로 필자는 과거에 std::queue를 여러 개 선언하여 메모리 초과를 받는 억까를 당한적이 있다. (https://codeforces.com/contest/1896/submission..

template struct Queue { std::vector head; std::vector tail; [[nodiscard]] int size() const { return int(head.size()) + int(tail.size()); } [[nodiscard]] bool empty() const { return size() == 0; } [[nodiscard]] const T& operator [] (int index) const { assert(0

template struct Deque { std::vector head; std::vector tail; [[nodiscard]] int size() const { return int(head.size()) + int(tail.size()); } [[nodiscard]] bool empty() const { return size() == 0; } [[nodiscard]] T& operator[](int index) { assert(0

template struct SlidingDeque { F func; std::vector head; std::vector tail; std::vector fhead; std::vector ftail; SlidingDeque(const F& _func = F {}) : func(_func) { void(0); } [[nodiscard]] int size() const { return int(head.size()) + int(tail.size()); } [[nodiscard]] bool empty() const { return size() == 0; } [[nodiscard]] const T& operator [] (int index) const { assert(0