test/aoj/ALDS1_9_C_persistent_leftist_heap.test.cpp

View this file on GitHub
Last update: 2023-07-03 22:05:02+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C

Depends on

Code

#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;
}