// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/double_ended_priority_queue
#include "../../../src/ds/dq/p/lib.hpp"
#include "../../../src/util/alias/others/lib.hpp"
using namespace tifa_libs;
int main() {
std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);
u32 _tests = 1;
flt_ (u32, _test, 1, _tests + 1) {
u32 n, q;
std::cin >> n >> q;
vec<int> a(n);
for (auto& x : a) std::cin >> x;
make_minmax_heap(begin(a), end(a));
while (q--) {
int t;
std::cin >> t;
if (t == 0) {
int x;
std::cin >> x;
a.push_back(x);
push_minmax_heap(begin(a), end(a));
} else if (t == 1) {
pop_minmax_heap_min(begin(a), end(a));
std::cout << a.back() << '\n';
a.pop_back();
} else {
pop_minmax_heap_max(begin(a), end(a));
std::cout << a.back() << '\n';
a.pop_back();
}
}
}
return 0;
}
#line 1 "test/cpv/library-checker-datastructure/double_ended_priority_queue.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/double_ended_priority_queue
#line 2 "src/ds/dq/p/lib.hpp"
#line 2 "src/util/alias/num/lib.hpp"
#line 2 "src/util/util/lib.hpp"
// https://github.com/Tiphereth-A/CP-lib
#include <bits/extc++.h>
// clang-format off
namespace tifa_libs {
#define CEXP constexpr
#define CEXPE constexpr explicit
#define CR const&
#define CP const*
#define PC *const
#define CPC const*const
#define TPN typename
#define NE noexcept
#define CNE const noexcept
#define ND [[nodiscard]]
#define cT_(...) std::conditional_t<sizeof(__VA_ARGS__) <= sizeof(size_t) * 2, __VA_ARGS__, __VA_ARGS__ CR>
// NOLINTNEXTLINE(misc-const-correctness)
#define flt_(T, i, l, r, ...) for (T i = (l), i##e = (r)__VA_OPT__(, ) __VA_ARGS__; i < i##e; ++i)
#define retif_(cond, if_true, ...) if cond return if_true __VA_OPT__(; else return __VA_ARGS__)
#ifdef ONLINE_JUDGE
#undef assert
#define assert(x) 42
#endif
using namespace std::ranges;
using namespace std::literals;
template <class T>
CEXP T abs(T x) NE { retif_((x < 0), -x, x); }
} // namespace tifa_libs
// clang-format on
#line 4 "src/util/alias/num/lib.hpp"
// clang-format off
namespace tifa_libs {
#define mk0_(w, t) using w = t; using c##w = const t
#define mk_(w, t) mk0_(w, t); CEXP w operator""_##w(unsigned long long x) NE { return (w)x; }
mk_(i8, int8_t) mk_(u8, uint8_t) mk_(i16, int16_t) mk_(u16, uint16_t) mk_(i32, int32_t) mk_(u32, uint32_t) mk_(i64, int64_t) mk_(u64, uint64_t) mk_(isz, ssize_t) mk_(usz, size_t) mk_(chr, char) mk_(schr, signed char) mk_(uchr, unsigned char) mk_(sint, signed) mk_(uint, unsigned);
mk0_(i128, __int128_t); mk0_(u128, __uint128_t); mk0_(f32, float); mk0_(f64, double); mk0_(f128, long double);
#undef mk0_
#undef mk_
} // namespace tifa_libs
// clang-format on
#line 4 "src/ds/dq/p/lib.hpp"
namespace tifa_libs {
// Copyright Malte Skarupke 2020.
// Distributed under the Boost Software License, Version 1.0.
// (See http://www.boost.org/LICENSE_1_0.txt)
namespace depq_impl_ {
CEXP int hib_(u32 i) NE { return std::bit_width(i) - 1; }
CEXP bool is_minni(u32 l) NE { return (hib_(l) & 1) == 0; }
CEXP bool is_mini(u32 i) NE { return is_minni(i + 1); }
CEXP u32 gpidx_(u32 i) NE { return (i - 3) / 4; }
CEXP u32 pidx_(u32 i) NE { return (i - 1) / 2; }
CEXP u32 ch1idx_(u32 i) NE { return (i * 2) + 1; }
CEXP u32 gchls_idx_(u32 i) NE { return (i * 4) + 6; }
template <class I, class C>
CEXP u32 s_dec_(I b, u32 l, u32 ch1, u32 gch1, C&& c) NE {
if (cu32 ch2 = ch1 + 1; gch1 >= l) return ch1 + (ch2 != l && c(b[ch2], b[ch1]));
else if (cu32 gch2 = gch1 + 1; gch2 == l) {
retif_((c(b[gch1], b[ch2])), gch1, ch2);
} else if (cu32 gchm = gch1 + !!c(b[gch2], b[gch1]), gch3 = gch2 + 1; gch3 == l) {
retif_((c(b[gchm], b[ch2])), gchm, ch2);
} else retif_((c(b[gchm], b[gch3])), gchm, gch3);
}
template <class I, class C>
CEXP u32 l_dec_(I b, u32 l, u32 ch1, u32 gch1, C&& c) NE {
if (cu32 ch2 = ch1 + 1; gch1 >= l) return ch1 + (ch2 != l && c(b[ch1], b[ch2]));
else if (cu32 gch2 = gch1 + 1; gch2 == l) {
retif_((c(b[ch2], b[gch1])), gch1, ch2);
} else if (cu32 gchm = gch1 + !!c(b[gch1], b[gch2]), gch3 = gch2 + 1; gch3 == l) {
retif_((c(b[ch2], b[gchm])), gchm, ch2);
} else retif_((c(b[gchm], b[gch3])), gch3, gchm);
}
template <class I, class C>
CEXP void pdmin_(I b, TPN std::iterator_traits<I>::value_type v, u32 i, u32 l, C&& c) NE {
for (;;)
if (cu32 gch_lst = gchls_idx_(i); gch_lst < l) {
auto it = b + gch_lst;
u32 h1m = gch_lst - 2 - !!c(it[-3], it[-2]),
h2m = gch_lst - !!c(it[-1], it[0]),
s = c(b[h2m], b[h1m]) ? h2m : h1m;
if (!c(b[s], v)) break;
b[i] = std::move(b[s]);
if (cu32 p = pidx_(i = s); c(b[p], v)) swap(b[p], v);
} else {
u32 ch1 = ch1idx_(i);
if (ch1 >= l) break;
u32 gch1 = gch_lst - 3, s = s_dec_(b, l, ch1, gch1, c);
if (!c(b[s], v)) break;
if (b[i] = std::move(b[s]); (i = s) < gch1) break;
if (cu32 p = pidx_(i); c(b[p], v)) b[i] = std::move(b[p]), i = p;
break;
}
b[i] = std::move(v);
}
template <class I, class C>
CEXP void pdmin_1ch_(I b, u32 i, C&& c) NE {
if (cu32 ch = ch1idx_(i); c(b[ch], b[i])) swap(b[i], b[ch]);
}
template <class I, class C>
CEXP void pdmin_1lvl_(I b, u32 i, C&& c) NE {
if (cu32 ch1 = ch1idx_(i), chs = ch1 + !!c(b[ch1 + 1], b[ch1]); c(b[chs], b[i])) swap(b[i], b[chs]);
}
template <class I, class C>
CEXP void pdmax_(I b, TPN std::iterator_traits<I>::value_type v, u32 i, u32 l, C&& c) NE {
for (;;)
if (cu32 gch_lst = gchls_idx_(i); gch_lst < l) {
auto it = b + gch_lst;
u32 h1m = gch_lst - 2 - !!c(it[-2], it[-3]),
h2m = gch_lst - !!c(it[0], it[-1]),
s = c(b[h1m], b[h2m]) ? h2m : h1m;
if (!c(v, b[s])) break;
b[i] = std::move(b[s]);
if (cu32 p = pidx_(i = s); c(v, b[p])) swap(b[p], v);
} else {
cu32 ch1 = ch1idx_(i);
if (ch1 >= l) break;
cu32 gch1 = gch_lst - 3, s = l_dec_(b, l, ch1, gch1, c);
if (!c(v, b[s])) break;
if (b[i] = std::move(b[s]); (i = s) < gch1) break;
if (cu32 p = pidx_(i); c(v, b[p])) b[i] = std::move(b[p]), i = p;
break;
}
b[i] = std::move(v);
}
template <class I, class C>
CEXP void pdmax_1ch_(I b, u32 i, C&& c) NE {
if (cu32 ch = ch1idx_(i); c(b[i], b[ch])) swap(b[i], b[ch]);
}
template <class I, class C>
CEXP void pdmax_1lvl_(I b, u32 i, C&& c) NE {
cu32 ch1 = ch1idx_(i), chb = ch1 + !!c(b[ch1], b[ch1 + 1]);
if (c(b[i], b[chb])) swap(b[i], b[chb]);
}
} // namespace depq_impl_
template <class I, class C = std::less<>>
CEXP bool is_minmax_heap(I begin, I end, C&& comp = C{}) NE {
cu32 l = u32(end - begin);
auto f = [](u32 i, auto cf) NE {
cu32 ch1 = depq_impl_::ch1idx_(i), ch2 = ch1 + 1,
gch1 = depq_impl_::ch1idx_(ch1),
gch2 = gch1 + 1,
gch3 = depq_impl_::ch1idx_(ch2),
gch4 = gch3 + 1;
return cf(ch1) && cf(ch2) && cf(gch1) && cf(gch2) && cf(gch3) && cf(gch4);
};
flt_ (u32, i, 0, l)
if (depq_impl_::is_mini(i)) {
if (!f(i, [&](u32 c) { return c >= l || !comp(begin[c], begin[i]); })) return false;
} else if (!f(i, [&](u32 c) { return c >= l || !comp(begin[i], begin[c]); })) return false;
return true;
}
template <common_range R, class C = std::less<>>
CEXP bool is_minmax_heap(R CR r, C&& comp = C{}) NE { return is_minmax_heap(begin(r), end(r), std::forward<C>(comp)); }
template <class I, class C = std::less<>>
void push_minmax_heap(I begin, I end, C&& comp = C{}) NE {
cu32 len = u32(end - begin), parent = depq_impl_::pidx_(len - 1);
u32 idx = len - 1;
TPN std::iterator_traits<I>::value_type value = std::move(end[-1]);
if (depq_impl_::is_minni(len)) {
if (idx == 0) static_cast<void>(0);
else if (comp(begin[parent], value)) {
begin[idx] = std::move(begin[parent]), idx = parent;
goto push_up_max;
} else {
for (;;) {
if (cu32 gp = depq_impl_::gpidx_(idx); comp(value, begin[gp])) begin[idx] = std::move(begin[gp]), idx = gp;
else break;
push_up_min:
if (!idx) break;
}
}
} else if (comp(value, begin[parent])) {
begin[idx] = std::move(begin[parent]), idx = parent;
goto push_up_min;
} else
push_up_max:
while (idx > 2)
if (cu32 gp = depq_impl_::gpidx_(idx); comp(begin[gp], value)) begin[idx] = std::move(begin[gp]), idx = gp;
else break;
begin[idx] = std::move(value);
}
template <common_range R, class C = std::less<>>
CEXP bool push_minmax_heap(R CR r, C&& comp = C{}) NE { return push_minmax_heap(begin(r), end(r), std::forward<C>(comp)); }
template <class I, class C = std::less<>>
CEXP void pop_minmax_heap_min(I begin, I end, C&& comp = C{}) NE {
if (cu32 l = u32(end - begin) - 1; l == 0) return;
else depq_impl_::pdmin_(begin, std::exchange(end[-1], std::move(begin[0])), 0, l, comp);
}
template <common_range R, class C = std::less<>>
CEXP bool pop_minmax_heap_min(R CR r, C&& comp = C{}) NE { return pop_minmax_heap_min(begin(r), end(r), std::forward<C>(comp)); }
template <class I, class C = std::less<>>
CEXP void pop_minmax_heap_max(I begin, I end, C&& comp = C{}) NE {
cu32 l = u32(end - begin) - 1;
if (l <= 1) return;
cu32 idx = 1 + !!comp(begin[1], begin[2]);
depq_impl_::pdmax_(begin, std::exchange(end[-1], std::move(begin[idx])), idx, l, std::forward<C>(comp));
}
template <common_range R, class C = std::less<>>
CEXP bool pop_minmax_heap_max(R CR r, C&& comp = C{}) NE { return pop_minmax_heap_max(begin(r), end(r), std::forward<C>(comp)); }
template <class I, class C = std::less<>>
CEXP void make_minmax_heap(I begin, I end, C&& comp = C{}) NE {
cu32 l = u32(end - begin);
u32 idx = l / 2;
if (idx == 0) return;
if ((l & 1) == 0) {
if (--idx; depq_impl_::is_mini(idx)) depq_impl_::pdmin_1ch_(begin, idx, comp);
else depq_impl_::pdmax_1ch_(begin, idx, comp);
if (idx == 0) return;
}
if (l != 4) {
for (cu32 lidx_ngch = l / 4;;) {
const auto hib = depq_impl_::hib_(idx);
cu32 loplim = max(lidx_ngch, (1_u32 << hib) - 1);
if (--idx; hib & 1)
for (;; --idx) {
if (depq_impl_::pdmax_1lvl_(begin, idx, comp); idx == loplim) break;
}
else {
for (;; --idx) {
if (depq_impl_::pdmin_1lvl_(begin, idx, comp); idx == loplim) break;
}
if (idx == 0) return;
}
if (idx == lidx_ngch) break;
}
}
const auto hib = depq_impl_::hib_(idx);
switch (u32 loplim = (1_u32 << hib) - 1; hib & 1)
for (;;) {
case 0:
for (;;) {
--idx;
depq_impl_::pdmin_(begin, std::move(begin[idx]), idx, l, comp);
if (idx == loplim) break;
}
if (idx == 0) return;
loplim /= 2;
[[fallthrough]];
case 1:
for (;;) {
--idx;
depq_impl_::pdmax_(begin, std::move(begin[idx]), idx, l, comp);
if (idx == loplim) break;
}
loplim /= 2;
}
}
template <common_range R, class C = std::less<>>
CEXP bool make_minmax_heap(R CR r, C&& comp = C{}) NE { return make_minmax_heap(begin(r), end(r), std::forward<C>(comp)); }
} // namespace tifa_libs
#line 2 "src/util/alias/others/lib.hpp"
#line 2 "src/util/consts/lib.hpp"
#line 4 "src/util/consts/lib.hpp"
// clang-format off
namespace tifa_libs {
using std::numbers::pi_v;
template <std::floating_point FP>
inline FP eps_v = std::sqrt(std::numeric_limits<FP>::epsilon());
template <std::floating_point FP>
CEXP void set_eps(FP v) NE { eps_v<FP> = v; }
CEXP u32 TIME = ((__TIME__[0] & 15) << 20) | ((__TIME__[1] & 15) << 16) | ((__TIME__[3] & 15) << 12) | ((__TIME__[4] & 15) << 8) | ((__TIME__[6] & 15) << 4) | (__TIME__[7] & 15);
CEXP auto STR2U16 = [] { std::array<u32, 65536> table{}; table.fill(-1_u32); flt_ (u32, i, 48, 58) flt_ (u32, j, 48, 58) table[i << 8 | j] = (j & 15) * 10 + (i & 15); return table; }();
inline const auto fn_0 = [](auto&&...) NE {};
inline const auto fn_is0 = [](auto x) NE { return x == 0; };
} // namespace tifa_libs
// clang-format on
#line 4 "src/util/alias/others/lib.hpp"
namespace tifa_libs {
template <class T>
struct chash {
CEXP static u64 C = u64(pi_v<f128> * 2e18) | 71;
CEXP u64 operator()(T x) CNE { return __builtin_bswap64(((u64)x ^ TIME) * C); }
};
// clang-format off
#define mk_(w, t) using w = t; using c##w = const t;
mk_(strn, std::string) mk_(strnv, std::string_view)
#undef mk_
template <class T> struct edge_t { T w; u32 u, v; CEXP auto operator<=>(edge_t CR) const = default; }; template <class T> using cedge_t = const edge_t<T>;
template <class T> struct pt3 { T _0, _1, _2; CEXP auto operator<=>(pt3 CR) const = default; }; template <class T> using cpt3 = const pt3<T>;
template <class T> struct pt4 { T _0, _1, _2, _3; CEXP auto operator<=>(pt4 CR) const = default; }; template <class T> using cpt4 = const pt4<T>;
#define mkT_(w, t, ...) template <class T> using w = t __VA_OPT__(, ) __VA_ARGS__; template <class T> using c##w = const t __VA_OPT__(, ) __VA_ARGS__;
mkT_(ptt, std::pair<T, T>) mkT_(alc, std::pmr::polymorphic_allocator<T>) mkT_(vec, std::vector<T>) mkT_(vvec, vec<vec<T>>) mkT_(v3ec, vvec<vec<T>>) mkT_(vecpt, vec<ptt<T>>) mkT_(vvecpt, vvec<ptt<T>>) mkT_(ptvec, ptt<vec<T>>) mkT_(ptvvec, ptt<vvec<T>>)
#undef mkT_
template <class T> using itl = std ::initializer_list<T>;
template <class T, usz ext = std::dynamic_extent> using spn = std::span<T const, ext>;
template <class T, usz N> using arr = std::array<T, N>; template <class T, usz N> using carr = std::array<const T, N>;
template <class U, class T> using vecp = vec<std::pair<U, T>>; template <class U, class T> using vvecp = vvec<std::pair<U, T>>;
template <class U, class T> using vvecp = vvec<std::pair<U, T>>; template <class U, class T> using vvvecp = vvec<vvec<std::pair<U, T>>>;
#ifdef PB_DS_ASSOC_CNTNR_HPP
template <class T, class C = std::less<T>> using set = __gnu_pbds::tree<T, __gnu_pbds::null_type, C>;
template <class K, class V, class C = std::less<K>> using map = __gnu_pbds::tree<K, V, C>;
// hset<u64> s({}, {}, {}, {}, {1<<16});
template <class T, class HF = chash<T>> using hset = __gnu_pbds::gp_hash_table<T, __gnu_pbds::null_type, HF>;
// hmap<u64, int> s({}, {}, {}, {}, {1<<16});
template <class K, class V, class HF = chash<K>> using hmap = __gnu_pbds::gp_hash_table<K, V, HF>;
#else
using std::set, std::map;
template <class T, class HF = chash<T>> using hset = std::unordered_set<T, HF>;
template <class K, class V, class HF = chash<K>> using hmap = std::unordered_map<K, V, HF>;
#endif
#ifdef PB_DS_PRIORITY_QUEUE_HPP
template <class T, class C = std::less<T>> using pq = __gnu_pbds::priority_queue<T, C>;
#else
template <class T, class C = std::less<T>> using pq = std::priority_queue<T, vec<T>, C>;
#endif
template <class T> using pqg = pq<T, std::greater<T>>;
// clang-format on
#define mk1_(V, A, T) using V##A = V<T>;
#define mk_(V, A, T) mk1_(V, A, T) mk1_(c##V, A, T)
#define mk(A, T) mk_(edge_t, A, T) mk_(ptt, A, T) mk_(pt3, A, T) mk_(pt4, A, T) mk_(vec, A, T) mk_(vvec, A, T) mk_(v3ec, A, T) mk_(vecpt, A, T) mk_(vvecpt, A, T) mk_(ptvec, A, T) mk_(ptvvec, A, T) mk1_(spn, A, T) mk1_(itl, A, T)
mk(b, bool) mk(c, chr) mk(i, i32) mk(u, u32) mk(ii, i64) mk(uu, u64) mk(t, isz) mk(z, usz) mk(f, f32) mk(d, f64) mk(s, strn);
#undef mk
#undef mk_
#undef mk1_
} // namespace tifa_libs
#line 4 "test/cpv/library-checker-datastructure/double_ended_priority_queue.cpp"
using namespace tifa_libs;
int main() {
std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);
u32 _tests = 1;
flt_ (u32, _test, 1, _tests + 1) {
u32 n, q;
std::cin >> n >> q;
vec<int> a(n);
for (auto& x : a) std::cin >> x;
make_minmax_heap(begin(a), end(a));
while (q--) {
int t;
std::cin >> t;
if (t == 0) {
int x;
std::cin >> x;
a.push_back(x);
push_minmax_heap(begin(a), end(a));
} else if (t == 1) {
pop_minmax_heap_min(begin(a), end(a));
std::cout << a.back() << '\n';
a.pop_back();
} else {
pop_minmax_heap_max(begin(a), end(a));
std::cout << a.back() << '\n';
a.pop_back();
}
}
}
return 0;
}
test/cpv/library-checker-datastructure/double_ended_priority_queue.cpp