Submit Info #26926

Problem Lang User Status Time Memory
Persistent Queue cpp hly1204 AC 832 ms 619.80 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 500 ms 355.80 MiB
example_00 AC 1 ms 0.67 MiB
half_rot_killer_00 AC 603 ms 449.30 MiB
random_00 AC 224 ms 63.75 MiB
random_01 AC 273 ms 76.80 MiB
random_02 AC 25 ms 9.30 MiB
random_2_00 AC 308 ms 93.67 MiB
random_2_01 AC 385 ms 115.52 MiB
random_2_02 AC 31 ms 13.12 MiB
random_3_00 AC 464 ms 331.17 MiB
random_3_01 AC 548 ms 391.67 MiB
random_3_02 AC 56 ms 37.42 MiB
two_stacks_killer_00 AC 832 ms 619.80 MiB

#ifndef LOCAL #define NDEBUG #endif #include <algorithm> #include <cassert> #include <cstring> #include <functional> #include <initializer_list> #include <iostream> #include <memory> #include <queue> #include <random> #include <vector> template <typename Type, typename Comp = std::less<>> struct PersistentTreap { public: static int get_random() { static std::random_device rd; static std::mt19937 gen(rd()); static std::uniform_int_distribution<int> dis(0, 1919810); return dis(gen); } struct Node { std::shared_ptr<Node> l, r; Type it; // item int sz, rk; // size and rank Node(const Type &it) : l(nullptr), r(nullptr), it(it), sz(1), rk(get_random()) {} Node(const std::shared_ptr<Node> &x) : l(x->l), r(x->r), it(x->it), sz(x->sz), rk(x->rk) {} ~Node() {} }; using pt = PersistentTreap; using sp = std::shared_ptr<Node>; PersistentTreap() : rt(nullptr), cmp(Comp()) {} PersistentTreap(Comp cmp) : rt(nullptr), cmp(cmp) {} PersistentTreap(const pt &rhs) : rt(rhs.rt), cmp(rhs.cmp) {} pt &operator=(const pt &rhs) { if (&rhs != this) rt = rhs.rt; return *this; } int size() const { return rt == nullptr ? 0 : rt->sz; } void is_empty() const { return rt == nullptr; } //----- binary search tree int get_rank(const Type &it) const { // how many items less than it auto x = rt; int res = 0; while (x != nullptr) { if (cmp(it, x->it)) { x = x->l; } else if (cmp(x->it, it)) { res += get_size(x->l) + 1; x = x->r; } else { x = x->l; } } return res; } const Type *select(int k) const { // 0...size()-1 auto x = rt; while (get_size(x->l) != k) { if (get_size(x->l) < k) { k -= get_size(x->l) + 1; x = x->r; } else { x = x->l; } } return &x->it; } const Type *pred(const Type &it) const { // lower_bound < const Type *res = nullptr; auto x = rt; while (x != nullptr) { if (cmp(x->it, it)) { res = &x->it, x = x->r; } else { x = x->l; } } return res; } const int *succ(const Type &it) const { // upper_bound > const Type *res = nullptr; auto x = rt; while (x != nullptr) { if (cmp(it, x->it)) { res = &x->it, x = x->l; } else { x = x->r; } } return res; } //----- binary search tree std::pair<pt, pt> split_at_value(const Type &it) { pt x, y; std::tie(x.rt, y.rt) = split_at_value(rt, it); return {x, y}; } std::pair<pt, pt> split_at_rank(const Type &it) { pt x, y; std::tie(x.rt, y.rt) = split_at_rank(rt, it); return {x, y}; } pt join(const pt &rhs) { // assume maxitem(this) <= minitem(rhs) or you don't care about pt res; auto [x1, y1] = split_at_rank(rt, size()); auto [x2, y2] = split_at_rank(rhs.rt, 0); res.rt = join(x1, y2); return res; } pt insert_at_value(const Type &it) { pt res; res.rt = insert_at_value(rt, it); return res; } pt insert_at_rank(int k, const Type &it) { // not instead pt res; res.rt = insert_at_rank(rt, k, it); return res; } pt delete_at_value(const Type &it) { pt res; res.rt = delete_at_value(rt, it); return res; } pt delete_at_rank(int k) { pt res; res.rt = delete_at_rank(rt, k); return res; } static sp left_rotate(sp x) { /* x b / \ / \ a b => x d / \ / \ c d a c */ sp b = x->r; x->r = b->l, b->l = x; b->sz = x->sz; fix_size(x); return b; } static sp right_rotate(sp x) { /* x a / \ / \ a b => c x / \ / \ c d d b */ sp a = x->l; x->l = a->r, a->r = x; a->sz = x->sz; fix_size(x); return a; } static sp delete_root(sp x) { if (x->l == x->r) return nullptr; sp y; if (get_rk(x->l) < get_rk(x->r)) { x->r = std::make_shared<Node>(x->r); y = left_rotate(x); y->l = delete_root(x); } else { x->l = std::make_shared<Node>(x->l); y = right_rotate(x); y->r = delete_root(x); } fix_size(y); return y; } static sp insert_at_rank(sp x, int k, const Type &it) { if (x == nullptr) return std::make_shared<Node>(it); x = std::make_shared<Node>(x); ++x->sz; if (k <= get_size(x->l)) { x->l = insert_at_rank(x->l, k, it); if (x->rk < x->l->rk) return right_rotate(x); } else { x->r = insert_at_rank(x->r, k - get_size(x->l) - 1, it); if (x->rk < x->r->rk) return left_rotate(x); } return x; } static sp delete_at_rank(sp x, int k) { x = std::make_shared<Node>(x); if (k == get_size(x->l)) return delete_root(x); if (k < get_size(x->l)) { x->l = delete_at_rank(x->l, k); } else { x->r = delete_at_rank(x->r, k - get_size(x->l) - 1); } fix_size(x); return x; } sp insert_at_value(sp x, const Type &it) { if (x == nullptr) return std::make_shared<Node>(it); x = std::make_shared<Node>(x); ++x->sz; if (cmp(it, x->it)) { x->l = insert_at_value(x->l, it); if (x->rk < x->l->rk) return right_rotate(x); } else { x->r = insert_at_value(x->r, it); if (x->rk < x->r->rk) return left_rotate(x); } return x; } sp delete_at_value(sp x, const Type &it) { if (x == nullptr) return nullptr; x = std::make_shared<Node>(x); if (cmp(it, x->it)) { x->l = delete_at_value(x->l, it); fix_size(x); return x; } else if (cmp(x->it, it)) { x->r = delete_at_value(x->r, it); fix_size(x); return x; } else { return delete_root(x); } } static sp join(sp x, sp y) { if (x == nullptr) return y; if (y == nullptr) return x; if (x->rk < y->rk) { y->l = join(x, y->l); fix_size(y); return y; } else { x->r = join(x->r, y); fix_size(x); return x; } } static std::pair<sp, sp> split_at_rank(sp x, int k) { // first tree have k items if (x == nullptr) return {nullptr, nullptr}; x = std::make_shared<Node>(x); if (k <= get_size(x->l)) { auto [y, z] = split_at_rank(x->l, k); x->l = z; fix_size(x); return {y, x}; } else { auto [y, z] = split_at_rank(x->r, k - get_size(x->l) - 1); x->r = y; fix_size(x); return {x, z}; } } std::pair<sp, sp> split_at_value(sp x, const Type &it) { if (x == nullptr) return {nullptr, nullptr}; x = std::make_shared<Node>(x); if (cmp(it, x->it)) { auto [y, z] = split_at_value(x->l, it); x->l = z; fix_size(x); return {y, x}; } else { auto [y, z] = split_at_value(x->r, it); x->r = y; fix_size(x); return {x, z}; } } void walk() { walk(rt); std::cout << "walk_over\n"; } static void walk(const sp &x) { if (x != nullptr) { walk(x->l); std::cout << x->it << ' '; walk(x->r); } } private: sp rt; Comp cmp; static int get_rk(const sp &x) { return x == nullptr ? -1 : x->rk; } static int get_size(const sp &x) { return x == nullptr ? 0 : x->sz; } static void fix_size(sp &x) { x->sz = get_size(x->l) + get_size(x->r) + 1; } }; int main() { #ifdef LOCAL std::freopen("..\\in", "r", stdin), std::freopen("..\\out", "w", stdout); #endif std::ios::sync_with_stdio(false); std::cin.tie(0); int n; std::cin >> n; std::vector<PersistentTreap<int>> rt(n + 5); for (int i = 1; i <= n; ++i) { int opt, t, x; std::cin >> opt >> t; if (opt == 0) { std::cin >> x; rt[i] = rt[t + 1].insert_at_rank(rt[t + 1].size(), x); } else { std::cout << *rt[t + 1].select(0) << '\n'; rt[i] = rt[t + 1].delete_at_rank(0); } } return 0; }