This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#define PROBLEM \ "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C" #include <iostream> #include <queue> #include <string> #include <tuple> #include "../../heap/persistent_leftist_heap.hpp" #include "../../util/reverse_cmp.hpp" #define _overload(_1, _2, _3, _4, name, ...) name #define _rep1(Itr, N) _rep3(Itr, 0, N, 1) #define _rep2(Itr, a, b) _rep3(Itr, a, b, 1) #define _rep3(Itr, a, b, step) for (i64 Itr = a; Itr < b; Itr += step) #define repeat(...) _overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__) #define rep(...) repeat(__VA_ARGS__) #define ALL(X) begin(X), end(X) using namespace std; using i64 = long long; using u64 = unsigned long long; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); vector<PersistentLeftistHeap<i64>> que; que.push_back(PersistentLeftistHeap<i64>()); vector<int> query; string s; while (cin >> s, s != "end") { if (s == "insert") { query.push_back(1); i64 k; cin >> k; que.push_back(que.back().push(-k)); } else { query.push_back(0); que.push_back(que.back().pop()); } } rep(i, (i64)query.size()) { if (query[i] == 0) { cout << -que[i].peek() << '\n'; } } return 0; }
#line 1 "test/aoj/ALDS1_9_C_persistent_leftist_heap.test.cpp" #define PROBLEM \ "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C" #include <iostream> #include <queue> #include <string> #include <tuple> #line 1 "heap/persistent_leftist_heap.hpp" #include <cassert> #include <utility> template <class T> struct PersistentLeftistHeap { struct Node { T val; int sz; Node *ch[2]; Node(const T &val) : val(val), sz(1), ch{nullptr, nullptr} {}; Node(Node *ptr) : val(ptr->val), sz(ptr->sz), ch{ptr->ch[0], ptr->ch[1]} {}; static int size(const Node *u) { return u == nullptr ? 0 : u->sz; }; static Node *update(Node *u) { u->sz = size(u->ch[0]) + size(u->ch[1]) + 1; if (size(u->ch[0]) < size(u->ch[1])) std::swap(u->ch[0], u->ch[1]); return u; } }; Node *root; using Self = PersistentLeftistHeap; PersistentLeftistHeap() = default; PersistentLeftistHeap(Node *root) : root(root){}; int size() const { return Node::size(root); }; bool empty() const { return size() == 0; }; Node *meld(Node *h1, Node *h2) const { if (h1 == nullptr) { return h2; } else if (h2 == nullptr) { return h1; } else { if (h1->val > h2->val) std::swap(h1, h2); auto v = new Node(h1); v->ch[1] = meld(v->ch[1], h2); return Node::update(v); } }; Self merge_with(const Self h) const { return Self(root, h.root); }; Self push(const T &v) const { return Self(meld(root, new Node(v))); }; T peek() const { assert(!empty()); return root->val; }; Self pop() const { assert(!empty()); return Self(meld(root->ch[0], root->ch[1])); }; }; #line 1 "util/reverse_cmp.hpp" template <class T> struct RevCmp { T val; RevCmp(T val) : val(val){}; bool operator<(const RevCmp &rhs) const { return rhs.val < val; }; bool operator>(const RevCmp &rhs) const { return val < rhs.val; }; bool operator==(const RevCmp &rhs) const { return !(val < rhs.val || rhs.val < val); }; bool operator!=(const RevCmp &rhs) const { return val < rhs.val || rhs.val < val; }; bool operator<=(const RevCmp &rhs) const { return *this < rhs || *this == rhs; }; bool operator>=(const RevCmp &rhs) const { return *this > rhs || *this == rhs; }; RevCmp &operator=(const RevCmp &rhs) { val = rhs.val; return *this; }; T value() const { return val; }; }; #line 11 "test/aoj/ALDS1_9_C_persistent_leftist_heap.test.cpp" #define _overload(_1, _2, _3, _4, name, ...) name #define _rep1(Itr, N) _rep3(Itr, 0, N, 1) #define _rep2(Itr, a, b) _rep3(Itr, a, b, 1) #define _rep3(Itr, a, b, step) for (i64 Itr = a; Itr < b; Itr += step) #define repeat(...) _overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__) #define rep(...) repeat(__VA_ARGS__) #define ALL(X) begin(X), end(X) using namespace std; using i64 = long long; using u64 = unsigned long long; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); vector<PersistentLeftistHeap<i64>> que; que.push_back(PersistentLeftistHeap<i64>()); vector<int> query; string s; while (cin >> s, s != "end") { if (s == "insert") { query.push_back(1); i64 k; cin >> k; que.push_back(que.back().push(-k)); } else { query.push_back(0); que.push_back(que.back().pop()); } } rep(i, (i64)query.size()) { if (query[i] == 0) { cout << -que[i].peek() << '\n'; } } return 0; }