verify/yosupo/yosupo_double_ended_priority_queue.test.cpp

View this file on GitHub
Last update: 2024-06-25 02:44:34+09:00
Problem: https://judge.yosupo.jp/problem/double_ended_priority_queue

Depends on

data_structure/binary_search_tree.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/double_ended_priority_queue"

#include <bits/stdc++.h>
using namespace std;

#include "../../data_structure/binary_search_tree.hpp"

int main() {
    int N, Q;
    cin >> N >> Q;
    BinarySearchTree bst;
    while(N--) {
        int a;
        cin >> a;
        bst.insert(a);
    }
    while(Q--) {
        int q;
        cin >> q;
        if(q == 0) {
            int x;
            cin >> x;
            bst.insert(x);
        }
        if(q == 1) {
            int out = bst.minimum();
            bst.erase(out);
            cout << out << endl;
        }
        if(q == 2) {
            int out = bst.maximum();
            bst.erase(out);
            cout << out << endl;
        }
    }
}

#line 1 "verify/yosupo/yosupo_double_ended_priority_queue.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/double_ended_priority_queue"

#include <bits/stdc++.h>
using namespace std;

#line 1 "data_structure/binary_search_tree.hpp"
template<class T=int>
struct BinarySearchTree{
    struct Node{
        T val;
        Node* l = nullptr;
        Node* r = nullptr;
        Node* p = nullptr;
        Node(T x) : val(x) {}
    };

    Node* root = nullptr;

    Node* find(T x) {
        Node* cur = root;
        while(cur) {
            if(cur->val == x) return cur;
            if(cur->val < x) cur = cur->r;
            else cur = cur->l;
        }
        return cur;
    }

    void insert(T x) {
        Node* new_node = new Node(x);
        Node* cur = root;
        Node* pre = nullptr;
        while(cur) {
            pre = cur;
            if(cur->val < x) cur = cur->r;
            else cur = cur->l;
        }
        if(!pre) root = new_node;
        else if(pre->val < x) pre->r = new_node;
        else pre->l = new_node;
        new_node->p = pre;
    }

    bool erase(T x) {
        Node* del = find(x);
        if(!del) return false;
        if(!del->l) transplant(del, del->r);
        else if(!del->r) transplant(del, del->l);
        else {
            Node* nxt = del->r;
            while(nxt->l) nxt = nxt->l;
            if(del->r != nxt) {
                transplant(nxt, nxt->r);    
                nxt->r = del->r;
                nxt->r->p = nxt;
            }
            transplant(del, nxt);
            nxt->l = del->l;
            nxt->l->p = nxt;
        }
        delete del;
        return true;
    }

    void transplant(Node* u, Node* v) {
        if(u == root) root = v;
        else if(u == u->p->l) u->p->l = v;
        else u->p->r = v;
        if(v) v->p = u->p;
    }

    T minimum() {
        Node* cur = root;
        Node* pre = nullptr;
        while(cur) {
            pre = cur;
            cur = cur->l;
        }
        if(!pre) return -1;
        return pre->val;
    }

    T maximum() {
        Node* cur = root;
        Node* pre = nullptr;
        while(cur) {
            pre = cur;
            cur = cur->r;
        }
        if(!pre) return -1;
        return pre->val;
    }
};
#line 7 "verify/yosupo/yosupo_double_ended_priority_queue.test.cpp"

int main() {
    int N, Q;
    cin >> N >> Q;
    BinarySearchTree bst;
    while(N--) {
        int a;
        cin >> a;
        bst.insert(a);
    }
    while(Q--) {
        int q;
        cin >> q;
        if(q == 0) {
            int x;
            cin >> x;
            bst.insert(x);
        }
        if(q == 1) {
            int out = bst.minimum();
            bst.erase(out);
            cout << out << endl;
        }
        if(q == 2) {
            int out = bst.maximum();
            bst.erase(out);
            cout << out << endl;
        }
    }
}