CP-templates

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Misuki743/CP-templates

:heavy_check_mark: ds/doubleEndedPQ.cpp

Verified with

Code

template<class T>
struct doubleEndedPQ {
  priority_queue<pair<T, int>> mx;
  priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> mn;
  vector<bool> inPQ;
  int t = 0, _size = 0;
  void push(T x) {
    mn.push(make_pair(x, t)), mx.push(make_pair(x, t));
    inPQ.emplace_back(true);
    _size++, t++;
  }
  void clean() {
    while(!mn.empty() and !inPQ[mn.top().second]) mn.pop();
    while(!mx.empty() and !inPQ[mx.top().second]) mx.pop();
  }
  T min() { return mn.top().first; }
  T max() { return mx.top().first; }
  void popMin() {
    inPQ[mn.top().second] = false, _size--;
    clean();
  }
  void popMax() {
    inPQ[mx.top().second] = false, _size--;
    clean();
  }
  int size() { return _size; }
  bool empty() { return _size == 0; }
};
#line 1 "ds/doubleEndedPQ.cpp"
template<class T>
struct doubleEndedPQ {
  priority_queue<pair<T, int>> mx;
  priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> mn;
  vector<bool> inPQ;
  int t = 0, _size = 0;
  void push(T x) {
    mn.push(make_pair(x, t)), mx.push(make_pair(x, t));
    inPQ.emplace_back(true);
    _size++, t++;
  }
  void clean() {
    while(!mn.empty() and !inPQ[mn.top().second]) mn.pop();
    while(!mx.empty() and !inPQ[mx.top().second]) mx.pop();
  }
  T min() { return mn.top().first; }
  T max() { return mx.top().first; }
  void popMin() {
    inPQ[mn.top().second] = false, _size--;
    clean();
  }
  void popMax() {
    inPQ[mx.top().second] = false, _size--;
    clean();
  }
  int size() { return _size; }
  bool empty() { return _size == 0; }
};
Back to top page