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/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); LeftistHeap<RevCmp<i64>> que; string s; while (cin >> s, s != "end") { if (s == "insert") { i64 k; cin >> k; if (!que.empty() && que.peek().value() == k) que.push(k).pop().push(k).pop(); que.push(k); } else { cout << que.peek().value() << '\n'; que.pop(); } // cout << que.size() << endl; } return 0; }
#line 1 "test/aoj/ALDS1_9_C_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/leftist_heap.hpp" #include <cassert> #include <utility> // min heap // weight-biased leftist heap template <class T> struct LeftistHeap { struct Node { T val; int sz; Node *ch[2]; Node(T &val) : val(val), sz(1), ch{nullptr, nullptr} {}; static int size(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 = nullptr; LeftistHeap() = default; Node *meld(Node *h1, Node *h2) { if (h1 == nullptr) { return h2; } else if (h2 == nullptr) { return h1; } else { if (h1->val > h2->val) std::swap(h1, h2); h1->ch[1] = meld(h1->ch[1], h2); return Node::update(h1); } }; LeftistHeap &merge_with(LeftistHeap &h) { root = meld(root, h.root); h.root = nullptr; return *this; }; LeftistHeap &push(T val) { root = meld(root, new Node(val)); return *this; }; T peek() const { assert(root != nullptr); return root->val; }; LeftistHeap &pop() { assert(root != nullptr); auto [l, r] = root->ch; delete root; root = meld(l, r); return *this; }; int size() { return Node::size(root); }; bool empty() { return size() == 0; }; }; #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_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); LeftistHeap<RevCmp<i64>> que; string s; while (cin >> s, s != "end") { if (s == "insert") { i64 k; cin >> k; if (!que.empty() && que.peek().value() == k) que.push(k).pop().push(k).pop(); que.push(k); } else { cout << que.peek().value() << '\n'; que.pop(); } // cout << que.size() << endl; } return 0; }