test/library-checker/DataStructure/DoubleEndedPriorityQueue.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://judge.yosupo.jp/problem/double_ended_priority_queue
Link: View error logs on GitHub Actions

Depends on

Code

#define PROBLEM                                                                \
    "https://judge.yosupo.jp/problem/double_ended_priority_queue"
#include <bits/stdc++.h>

#include "library/superstd/Multiset.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    Multiset<int> s;
    s.scan(n);
    while (q--) {
        int t;
        std::cin >> t;
        switch (t) {
            case 0: {
                int x;
                std::cin >> x;
                s.insert(x);
                break;
            }
            case 1: {
                int a = s.pick_mn();
                std::cout << a << "\n";
                break;
            }
            case 2: {
                int a = s.pick_mx();
                std::cout << a << "\n";
                break;
            }
            default:
                std::unreachable();
        }
    }
}

#line 1 "test/library-checker/DataStructure/DoubleEndedPriorityQueue.test.cpp"
#define PROBLEM                                                                \
    "https://judge.yosupo.jp/problem/double_ended_priority_queue"
#include <bits/stdc++.h>

#line 1 "library/superstd/Multiset.hpp"
template <typename T> class Multiset {
    using u32 = std::uint32_t;
    u32 size_;

  public:
    std::map<T, u32> m;

    Multiset() : size_(0) {}

    void banpei() {
        insert(std::numeric_limits<T>::max() / 2);
        insert(std::numeric_limits<T>::min() / 2);
        size_ -= 2;
    }

    bool contains(const T &a) const { return m.contains(a); }
    u32 count(const T &a) { return contains(a) ? m[a] : 0; }
    u32 size() const { return size_; }
    void clear() {
        m.clear();
        size_ = 0;
    }

    void insert(const T &a, u32 k = 1) {
        if (!k)
            return;
        m[a] += k;
        size_ += k;
    }

    void erase(const T &a) {
        size_ -= count(a);
        m.erase(a);
    }
    void erase_k(const T &a, u32 k = 1) {
        if (count(a) <= k) {
            size_ -= count(a);
            erase(a);
        } else {
            m[a] -= k;
            size_ -= k;
        }
    }
    void erase1(const T &a) { erase_k(a, 1); }

    T min_value() const {
        assert(size());
        return m.begin()->first;
    }
    T max_value() const { // MaxValu
        assert(size());
        return m.rbegin()->first;
    }

    T pick_min() { // ピクミン
        T res = min_value();
        erase1(res);
        return res;
    }
    T pick_max() {
        T res = max_value();
        erase1(res);
        return res;
    }

    T lt(const T &a) const {
        assert(min_value() < a);
        return (--m.lower_bound(a))->first;
    }
    T leq(const T &a) const {
        assert(min_value() <= a);
        return (--m.upper_bound(a))->first;
    }
    T gt(const T &a) const {
        assert(max_value() > a);
        return m.upper_bound(a)->first;
    }
    T geq(const T &a) const {
        assert(max_value() >= a);
        return m.lower_bound(a)->first;
    }

    void scan(int n) {
        while (n--) {
            T a;
            std::cin >> a;
            insert(a);
        }
    }

    T pick_mn() { return pick_min(); }
    T pick_mx() { return pick_max(); }
};
#line 6 "test/library-checker/DataStructure/DoubleEndedPriorityQueue.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    Multiset<int> s;
    s.scan(n);
    while (q--) {
        int t;
        std::cin >> t;
        switch (t) {
            case 0: {
                int x;
                std::cin >> x;
                s.insert(x);
                break;
            }
            case 1: {
                int a = s.pick_mn();
                std::cout << a << "\n";
                break;
            }
            case 2: {
                int a = s.pick_mx();
                std::cout << a << "\n";
                break;
            }
            default:
                std::unreachable();
        }
    }
}