This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "data_structure/double_ended_priority_queue.hpp"
double_ended_priority_queue() = default // (1) double_ended_priority_queue(InputIterator first, InputIterator last) // (2)
空であるかを判定する。 $O(1)$
要素数を所得する。 $O(1)$
x を追加。 $O(\log{N})$
x
要素型 T のコンストラクタ引数をとり、直接構築で要素を追加する。 $O(\log{N})$
T
最小値を取り除く。 $O(\log{N})$
最大値を取り除く。 $O(\log{N})$
最小値を所得する。 $O(1)$
最大値を所得する。 $O(1)$
#pragma once #include <cassert> #include <vector> #include "../data_structure/removable_priority_queue.hpp" namespace ebi { template <class T> struct double_ended_priority_queue { public: double_ended_priority_queue() = default; template <class InputIterator> double_ended_priority_queue(InputIterator first, InputIterator last) { min = removable_priority_queue<T, std::vector<T>, std::greater<T>>( first, last); max = removable_priority_queue<T>(first, last); } bool empty() const { return min.empty() && max.empty(); } int size() const { assert(min.size() == max.size()); return min.size(); } void push(T x) { min.push(x); max.push(x); } template <class... Args> void emplace(Args &&...args) { min.emplace(std::forward<Args>(args)...); max.emplace(std::forward<Args>(args)...); return; } void pop_min() { T x = min.top(); min.pop(); max.remove(x); } void pop_max() { T x = max.top(); max.pop(); min.remove(x); } T get_min() { assert(!min.empty()); return min.top(); } T get_max() { assert(!max.empty()); return max.top(); } private: removable_priority_queue<T, std::vector<T>, std::greater<T>> min; removable_priority_queue<T> max; }; } // namespace ebi
#line 2 "data_structure/double_ended_priority_queue.hpp" #include <cassert> #include <vector> #line 2 "data_structure/removable_priority_queue.hpp" #include <functional> #include <queue> #line 6 "data_structure/removable_priority_queue.hpp" /* reference: https://twitter.com/maspy_stars/status/1436690222465486848 verify: https://atcoder.jp/contests/abc218/submissions/25800862 */ namespace ebi { template <class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type>> struct removable_priority_queue { private: void update() { while (!rm_que.empty() && que.top() == rm_que.top()) { que.pop(); rm_que.pop(); } return; } public: removable_priority_queue() = default; template <class InputIterator> removable_priority_queue(InputIterator first, InputIterator last) { que = std::priority_queue<T, Container, Compare>(first, last); } bool empty() const { return (size() == 0); } int size() const { return int(que.size() - rm_que.size()); } T top() { assert(!empty()); update(); return que.top(); } void pop() { assert(!empty()); update(); que.pop(); return; } void push(const T &x) { que.push(x); return; } template <class... Args> void emplace(Args &&...args) { que.emplace(std::forward<Args>(args)...); return; } void remove(const T &x) { rm_que.push(x); assert(que.size() >= rm_que.size()); return; } template <class... Args> void emplace_remove(Args &&...args) { rm_que.emplace(std::forward<Args>(args)...); assert(que.size() >= rm_que.size()); return; } private: std::priority_queue<T, Container, Compare> que, rm_que; }; } // namespace ebi #line 7 "data_structure/double_ended_priority_queue.hpp" namespace ebi { template <class T> struct double_ended_priority_queue { public: double_ended_priority_queue() = default; template <class InputIterator> double_ended_priority_queue(InputIterator first, InputIterator last) { min = removable_priority_queue<T, std::vector<T>, std::greater<T>>( first, last); max = removable_priority_queue<T>(first, last); } bool empty() const { return min.empty() && max.empty(); } int size() const { assert(min.size() == max.size()); return min.size(); } void push(T x) { min.push(x); max.push(x); } template <class... Args> void emplace(Args &&...args) { min.emplace(std::forward<Args>(args)...); max.emplace(std::forward<Args>(args)...); return; } void pop_min() { T x = min.top(); min.pop(); max.remove(x); } void pop_max() { T x = max.top(); max.pop(); min.remove(x); } T get_min() { assert(!min.empty()); return min.top(); } T get_max() { assert(!max.empty()); return max.top(); } private: removable_priority_queue<T, std::vector<T>, std::greater<T>> min; removable_priority_queue<T> max; }; } // namespace ebi