Double-Ended Priority Queue
(tests/stl/double-ended-priority-queue.test.cpp)

• View this file on GitHub
• Last update: 2025-03-03 00:33:48+09:00
• Problem: https://judge.yosupo.jp/problem/double_ended_priority_queue

最大値・最小値の取り出しができる優先度付きキュー。

priority_queue 2 本持ちで、片方は最大値を取り出すためのもの、もう片方は最小値を取り出すためのものを用意する。 …のが一般的っぽいが、 multiset 1 つでできるので、multiset で代用した。

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

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

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  multiset<int> s;
  rep(i, n) {
    int x;
    cin >> x;
    s.insert(x);
  }
  while (q--) {
    int t;
    cin >> t;
    if (t == 0) {
      int x;
      cin >> x;
      s.insert(x);
    }
    if (t == 1) {
      cout << *s.begin() << '\n';
      s.erase(s.begin());
    }
    if (t == 2) {
      cout << *s.rbegin() << '\n';
      s.erase(prev(s.end()));
    }
  }
  return 0;
}

#line 1 "tests/stl/double-ended-priority-queue.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

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

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  multiset<int> s;
  rep(i, n) {
    int x;
    cin >> x;
    s.insert(x);
  }
  while (q--) {
    int t;
    cin >> t;
    if (t == 0) {
      int x;
      cin >> x;
      s.insert(x);
    }
    if (t == 1) {
      cout << *s.begin() << '\n';
      s.erase(s.begin());
    }
    if (t == 2) {
      cout << *s.rbegin() << '\n';
      s.erase(prev(s.end()));
    }
  }
  return 0;
}

Back to top page