#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A" // #define PROBLEM "https://yukicoder.me/problems/no/649" #include #include namespace zawa { using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u8 = std::uint8_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using usize = std::size_t; } // namespace zawa #include #include #include #include namespace zawa { // 1-indexed template class PriorityProductSet { public: using V = G::Element; PriorityProductSet() = default; PriorityProductSet(usize K) : m_K{K} {} void insert(V&& v) { pushSmall(std::move(v)); adjust(); } void insert(const V& v) { insert(V{v}); } usize size() const { return m_small.size() + m_big.size(); } inline usize K() const { return m_K; } void setK(usize K) { m_K = K; adjust(); } std::optional product() const { return m_small.size() == K ? std::optional{m_sv} : std::nullopt; } std::optional productRemain() const { return m_small.size() == K ? std::optional{m_bv} : std::nullopt; } V productAll() const { return G::operation(m_sv, m_bv); } V popK() { assert(m_K >= 1u and size() >= m_K); V res = popSmall(); adjust(); return res; } private: std::priority_queue m_small; std::priority_queue, std::greater> m_big; V m_sv = G::identity(), m_bv = G::identity(); usize m_K = 0; void pushSmall(V&& v) { m_sv = G::operation(m_sv, v); m_small.push(std::move(v)); } V popSmall() { assert(m_small.size()); V res = m_small.top(); m_small.pop(); m_sv = G::operation(m_sv, G::inverse(res)); return res; } void pushBig(V&& v) { m_bv = G::operation(m_bv, v); m_big.push(std::move(v)); } V popBig() { assert(m_big.size()); V res = m_big.top(); m_big.pop(); m_bv = G::operation(m_bv, G::inverse(res)); return res; } void adjust() { while (m_small.size() > m_K) pushBig(popSmall()); while (m_small.size() < m_K and m_big.size()) pushSmall(popBig()); } }; } // namespace zawa struct G { using Element = long long; static Element identity() { return 0; } static Element operation(Element,Element) { return 0; } static Element inverse(Element) { return 0; } }; #include int Q, K; void solve() { std::cin >> Q >> K; zawa::PriorityProductSet set(K); while (Q--) { int t; std::cin >> t; if (t == 1) { long long v; std::cin >> v; set.insert(v); } else if (t == 2) { if (set.size() < (int)K) { std::cout << -1 << '\n'; } else { std::cout << set.popK() << '\n'; } } else { assert(false); } } } int main() { #ifdef ONLINE_JUDGE std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios::sync_with_stdio(false); solve(); #else std::cout << "Hello World\n"; #endif }