#line 1 "test/yukicoder/649__RBSTMultiSet.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/649" #line 2 "common/util.hpp" #line 2 "common/alias.hpp" #include #include using namespace std; // using namespace std::views; // using namespace boost::multiprecision; // --- 型エイリアス --- using ll = long long; using ull = unsigned long long; template using vec = vector; template using vvec = vector>; template using vvvec = vector>>; template using p_queue = priority_queue; template using rp_queue = priority_queue, greater>; using bint = boost::multiprecision::cpp_int; // --- 黒魔術 --- #define int ll // --- 制御マクロ --- #define rep(i, n) for (ll i = 0; i < n; ++i) #define all(v) begin(v), end(v) // #define BIT(n) (1LL << (n)) #define MAX(type) numeric_limits::max() #define MIN(type) numeric_limits::min() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define pb push_back #define mp make_pair #define fir first #define sec second // --- 定数 --- constexpr ll INF = 1LL << 60; // constexpr ll INF = numeric_limits::max(); inline signed bit_width(ll x) { return bit_width((ull)x); } inline ull bit_ceil(ll x) { return bit_ceil((ull)x); } #line 2 "common/concepts.hpp" #line 4 "common/concepts.hpp" template concept addable = requires(T a, T b) { { a + b } -> convertible_to; }; #line 5 "common/util.hpp" // --- Utils --- // 二分探索 template inline T bin_search(T ok, T ng, const function is_ok) { assert(is_ok(ok)); assert(!is_ok(ng)); assert(ok < ng); while (abs(ok - ng) > 1) { T mid = (ok + ng) / 2; if (is_ok(mid)) ok = mid; else ng = mid; } return ok; } // 順列全探索 inline void rep_perm(int n, function &)> f) { vec v(n); iota(v.begin(), v.end(), 0); do { f(v); } while (next_permutation(v.begin(), v.end())); } inline void rep_bit(int n, function f) { rep(i, 1LL << n) f(i); } // 配列 to string template inline string join(const vec &v, string sep = " ") { string res = ""; rep(i, v.size()) res += to_string(v[i]) + (i == v.size() - 1 ? "" : sep); return res; } template inline void join_out(ostream &os, const vec &v, string sep = " ", string end = "\n") { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? end : sep); } template inline void transform(vec &src, function f) { for (auto &val : src) f(val); } // ベース指定ceil inline ll ceil(ll x, ll base) { return (x + base - 1) / base * base; } // ベース指定floor inline ll floor(ll x, ll base) { return x / base * base; } // 合計値を求める // ll sum(const vec &v) { return accumulate(all(v), 0LL); } template T sum(const vec &v) { return accumulate(all(v), T()); } // 可変引数min template auto min(T... a) { return min(initializer_list>{a...}); } // 可変引数max template auto max(T... a) { return max(initializer_list>{a...}); } template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } // 3項間不等式 // 広義単調増加 inline bool is_increasing(int x, int y, int z) { return x <= y && y <= z; } // 半開区間[x, z)にyが含まれるか? inline bool is_contained(int x, int y, int z) { return x <= y && y < z; } // 頂点(x, y)が範囲に含まれるか inline bool is_contained(int H, int W, int x, int y) { return is_contained(0, x, H) && is_contained(0, y, W); } // rootに対し、aとbが同じ側にあるか (=は含まない) inline bool is_same_side(int root, int a, int b) { return (root < a) == (root < b); } // vector継承にする? template struct vec_accumulate : public vec { explicit vec_accumulate(vec &v) : vec(v.size()) { assert(v.size() > 0); this->at(0) = v[0]; for (int i = 1; i < v.size(); ++i) this->at(i) = this->at(i - 1) + v[i]; } // [0, i]の和 // なので、-1 <= i < size() T operator[](int i) { assert(is_contained(-1, i, this->size())); if (i == -1) return T(); return this->at(i); } }; // vector func template inline void unique_erase(vec &v) { sort(all(v)); v.erase(unique(all(v)), v.end()); } void io_setup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << std::fixed << std::setprecision(15); } #line 2 "datastructure/rbst_multiset.hpp" #line 4 "datastructure/rbst_multiset.hpp" template struct RBST { private: /// 乱数シード生成器 random_device rd; /// 乱数生成器 mt19937 mt; /// 単位元 T e; /// 演算 function F; protected: /// ノード struct node_t { /// ノードの値 T val; /// 部分木の大きさ size_t size; /// 部分木の総積 T sum; /// 左右の子 node_t *lch, *rch; /// 値のみによるノードの生成 node_t(T val): val(val), size(1), sum(val), lch(nullptr), rch(nullptr) {} /// 値と子によるノードの生成 node_t(T val, node_t* lch, node_t* rch): val(val), size(1), sum(val), lch(lch), rch(rch) {} }; /// ノードの値を取得 inline T val(const node_t* const t) const { return t ? t->val : e; } inline size_t size(const node_t* const t) const { return t ? t->size : 0; } inline T sum(const node_t* const t) const { return t ? t->sum : e; } inline node_t* update(node_t* const t) const { t->size = size(t->lch) + size(t->rch) + 1; t->sum = F(F(sum(t->lch), val(t)), sum(t->rch)); return t; } public: RBST(T e, function F): mt(rd()), e(e), F(F) {} node_t* root = nullptr; inline node_t* merge(node_t* const l, node_t* const r) { if (!l || !r) return l ? l : r; if (mt() % (l->size + r->size) < l->size) { l->rch = merge(l->rch, r); return update(l); } else { r->lch = merge(l, r->lch); return update(r); } } inline pair split(node_t* const t, const size_t k) { if (!t) return {nullptr, nullptr}; if (k <= size(t->lch)) { auto p = split(t->lch, k); t->lch = p.second; return {p.first, update(t)}; } else { auto p = split(t->rch, k - size(t->lch) - 1); t->rch = p.first; return {update(t), p.second}; } } inline node_t* insert_at(node_t* t, const size_t k, T val) { auto [l, r] = split(t, k); return t = merge(merge(l, new node_t(val)), r); } inline void insert_at(const size_t k, T val) { if(!root) root = new node_t(val); else root = insert_at(root, k, val); } inline node_t* erase_at(node_t* t, const size_t k) { auto [l, r] = split(t, k); auto [ll, lr] = split(r, 1); return t = merge(l, lr); } inline void erase_at(const size_t k) { assert(root); assert(0 <= k); assert(k < root->size); if(root->size == 1) { delete root; root = nullptr; return; } root = erase_at(root, k); } inline T get_at(const node_t* const t, const size_t k) const { assert(t); assert(0 <= k); assert(k < t->size); if(k < size(t->lch)) return get_at(t->lch, k); if(k == size(t->lch)) return t->val; return get_at(t->rch, k - size(t->lch) - 1); } inline T get_at(const size_t k) const { return get_at(root, k); } inline T query(node_t* &t, const size_t l, const size_t r) { auto [left, mid_right] = split(t, l); auto [mid, right] = split(mid_right, r - l); T res = sum(mid); t = merge(merge(left, mid), right); return res; } inline T query(const size_t l, const size_t r) { return query(root, l, r); } inline size_t size() const { return size(root); } }; template struct RBSTMultiSet : public RBST { private: using node_t = typename RBST::node_t; public: RBSTMultiSet(): RBST(0, [](T a, T b){return a;}) {} size_t lower_bound(node_t* t, T val) { if(!t) return 0; if(val <= this->val(t)) return lower_bound(t->lch, val); return this->size(t->lch) + 1 + lower_bound(t->rch, val); } size_t lower_bound(T val) { return lower_bound(this->root, val); } size_t upper_bound(node_t* t, T val) { if(!t) return 0; if(val < t->val) return upper_bound(t->lch, val); return this->size(t->lch) + 1 + upper_bound(t->rch, val); } size_t upper_bound(T val) { return upper_bound(this->root, val); } void insert(T val) { this->insert_at(lower_bound(val), val); } size_t count(T val) { return upper_bound(val) - lower_bound(val); } bool contains(T val) { int idx = lower_bound(val); return idx < this->root->size && this->get_at(idx)->val == val; } void erase(T val) { int idx = lower_bound(val); if(idx < this->root->size && this->get_at(idx)->val == val) { this->erase_at(idx); } } }; template struct RBSTSet : public RBSTMultiSet { public: RBSTSet(): RBSTMultiSet() {} void insert(T val) { if(contains(val)) return; this->insert(val, lower_bound(val)); } }; #line 5 "test/yukicoder/649__RBSTMultiSet.test.cpp" signed main() { io_setup(); int Q, K; cin >> Q >> K; K--; RBSTMultiSet tree; rep(q, Q) { int type; cin >> type; if (type == 1) { int v; cin >> v; tree.insert(v); } else { if(K >= tree.size()) { cout << -1 << endl; continue; } cout << tree.get_at(K) << endl; tree.erase_at(K); } } }