verify/verify-yosupo-ds/yosupo-priority-set.test.cpp

• View this file on GitHub
• Last update: 2025-03-17 21:57:32+08:00
• Problem: https://judge.yosupo.jp/problem/double_ended_priority_queue

Depends on

• src/alfred/config/io-sync-off.hpp
• src/alfred/data_structure/priority-set.hpp

Code

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

#include "../../src/alfred/config/io-sync-off.hpp"
#include "../../src/alfred/data_structure/priority-set.hpp"
#include <iostream>

int main(int argc, char const *argv[]) {
    int n, q, opt, x;
    optimizeIO(), std::cin >> n >> q;
    PrioritySet<int, std::less<int>> P1;
    PrioritySet<int, std::greater<int>> P2;
    for (int i = 0; i < n; i++) {
        std::cin >> x;
        P1.insert(x);
        P2.insert(x);
    }
    while (q--) {
        std::cin >> opt;
        if (opt == 0) {
            std::cin >> x;
            P1.insert(x);
            P2.insert(x);
        } else if (opt == 1) {
            x = P2.top();
            std::cout << x << '\n';
            P1.erase(x), P2.erase(x);
        } else {
            x = P1.top();
            std::cout << x << '\n';
            P1.erase(x), P2.erase(x);
        }
    }
    return 0;
}

#line 1 "verify/verify-yosupo-ds/yosupo-priority-set.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/double_ended_priority_queue"

#line 1 "src/alfred/config/io-sync-off.hpp"
#include <bits/stdc++.h>

inline void optimizeIO(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
}
#line 1 "src/alfred/data_structure/priority-set.hpp"



#line 6 "src/alfred/data_structure/priority-set.hpp"

template <class T, class Comp = std::less<T>>
class PrioritySet { // warning: all erase operations must be legal.
private:
    std::priority_queue<T, std::vector<T>, Comp> data;
    std::priority_queue<T, std::vector<T>, Comp> erased;

public:
    PrioritySet(void) : data(), erased() {};
    PrioritySet(std::vector<T> &init) {
        for (auto &v : init) insert(v);
    }
    inline void insert(const T x) { data.push(x); }
    inline void erase(const T x) { erased.push(x); }
    inline const T &top(void) noexcept {
        // assert(data.size() >= erased.size());
        while (!erased.empty() && data.top() == erased.top()) {
            data.pop(), erased.pop();
        }
        return data.top();
    }
    inline size_t size(void) {
        return data.size() - erased.size();
    }
};


#line 6 "verify/verify-yosupo-ds/yosupo-priority-set.test.cpp"

int main(int argc, char const *argv[]) {
    int n, q, opt, x;
    optimizeIO(), std::cin >> n >> q;
    PrioritySet<int, std::less<int>> P1;
    PrioritySet<int, std::greater<int>> P2;
    for (int i = 0; i < n; i++) {
        std::cin >> x;
        P1.insert(x);
        P2.insert(x);
    }
    while (q--) {
        std::cin >> opt;
        if (opt == 0) {
            std::cin >> x;
            P1.insert(x);
            P2.insert(x);
        } else if (opt == 1) {
            x = P2.top();
            std::cout << x << '\n';
            P1.erase(x), P2.erase(x);
        } else {
            x = P1.top();
            std::cout << x << '\n';
            P1.erase(x), P2.erase(x);
        }
    }
    return 0;
}

Back to top page