test/library_checker/data_structure/double_ended_priority_queue.test.cpp

• View this file on GitHub
• Last update: 2024-11-15 15:44:55+09:00
• Problem: https://judge.yosupo.jp/problem/double_ended_priority_queue

Depends on

• Double Ended Priority Queue (lib/data_structure/double_ended_priority_queue.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/double_ended_priority_queue"
#include <iostream>

#include "../../../lib/data_structure/double_ended_priority_queue.hpp"

using namespace std;

int main(){
    int n, q; cin >> n >> q;
    DoubleEndedPriorityQueue<int> depq;
    for(int i = 0; i < n; i++){
        int s; cin >> s;
        depq.push(s);
    }
    while(q--){
        int t; cin >> t;
        if(t == 0){
            int x; cin >> x;
            depq.push(x);
        }else if(t == 1){
            cout << depq.get_min() << "\n";
            depq.pop_min();
        }else{
            cout << depq.get_max() << "\n";
            depq.pop_max();
        }
    }
}

#line 1 "test/library_checker/data_structure/double_ended_priority_queue.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/double_ended_priority_queue"
#include <iostream>

#line 2 "lib/data_structure/double_ended_priority_queue.hpp"

/**
 * @brief Double Ended Priority Queue
 */

#include <queue>
#include <vector>
#include <cassert>

template <typename T>
struct DoubleEndedPriorityQueue{
    std::priority_queue<T, std::vector<T>, std::greater<T>> min_q, removed_min;
    std::priority_queue<T> max_q, removed_max;
    DoubleEndedPriorityQueue(){ }

    void normalize(){
        while(!removed_min.empty() && min_q.top() == removed_min.top()) {
            removed_min.pop();
            min_q.pop();
        }
        while(!removed_max.empty() && max_q.top() == removed_max.top()) {
            removed_max.pop();
            max_q.pop();
        }
    }

    void push(const T &x){
        min_q.push(x);
        max_q.push(x);
    }

    void pop_min(){
        assert(!min_q.empty());
        normalize();
        removed_max.push(min_q.top());
        min_q.pop();
    }

    void pop_max(){
        assert(!max_q.empty());
        normalize();
        removed_min.push(max_q.top());
        max_q.pop();
    }

    T get_min(){
        assert(!min_q.empty());
        normalize();
        return min_q.top();
    }

    T get_max(){
        assert(!max_q.empty());
        normalize();
        return max_q.top();
    }
};
#line 5 "test/library_checker/data_structure/double_ended_priority_queue.test.cpp"

using namespace std;

int main(){
    int n, q; cin >> n >> q;
    DoubleEndedPriorityQueue<int> depq;
    for(int i = 0; i < n; i++){
        int s; cin >> s;
        depq.push(s);
    }
    while(q--){
        int t; cin >> t;
        if(t == 0){
            int x; cin >> x;
            depq.push(x);
        }else if(t == 1){
            cout << depq.get_min() << "\n";
            depq.pop_min();
        }else{
            cout << depq.get_max() << "\n";
            depq.pop_max();
        }
    }
}

Back to top page