test/aoj/ALDS1_9_C_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/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;
}