結果
問題 | No.649 ここでちょっとQK! |
ユーザー | ZOI-dayo |
提出日時 | 2024-05-31 23:27:58 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 502 ms / 3,000 ms |
コード長 | 10,048 bytes |
コンパイル時間 | 6,249 ms |
コンパイル使用メモリ | 400,416 KB |
実行使用メモリ | 12,928 KB |
最終ジャッジ日時 | 2024-05-31 23:28:13 |
合計ジャッジ時間 | 13,881 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 255 ms
6,944 KB |
testcase_04 | AC | 146 ms
12,800 KB |
testcase_05 | AC | 143 ms
12,928 KB |
testcase_06 | AC | 143 ms
12,800 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 1 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 1 ms
6,944 KB |
testcase_12 | AC | 194 ms
7,680 KB |
testcase_13 | AC | 193 ms
7,552 KB |
testcase_14 | AC | 192 ms
7,552 KB |
testcase_15 | AC | 209 ms
7,680 KB |
testcase_16 | AC | 212 ms
7,680 KB |
testcase_17 | AC | 237 ms
8,192 KB |
testcase_18 | AC | 249 ms
8,576 KB |
testcase_19 | AC | 281 ms
8,960 KB |
testcase_20 | AC | 318 ms
9,472 KB |
testcase_21 | AC | 333 ms
9,728 KB |
testcase_22 | AC | 358 ms
10,112 KB |
testcase_23 | AC | 389 ms
10,496 KB |
testcase_24 | AC | 438 ms
11,008 KB |
testcase_25 | AC | 459 ms
11,392 KB |
testcase_26 | AC | 502 ms
11,904 KB |
testcase_27 | AC | 3 ms
6,944 KB |
testcase_28 | AC | 3 ms
6,944 KB |
testcase_29 | AC | 3 ms
6,940 KB |
testcase_30 | AC | 199 ms
7,552 KB |
testcase_31 | AC | 198 ms
7,680 KB |
testcase_32 | AC | 2 ms
6,940 KB |
testcase_33 | AC | 2 ms
6,944 KB |
testcase_34 | AC | 2 ms
6,940 KB |
testcase_35 | AC | 1 ms
6,940 KB |
ソースコード
#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 <boost/multiprecision/cpp_int.hpp> #include <bits/stdc++.h> using namespace std; // using namespace std::views; // using namespace boost::multiprecision; // --- 型エイリアス --- using ll = long long; using ull = unsigned long long; template <typename T> using vec = vector<T>; template <typename T> using vvec = vector<vector<T>>; template <typename T> using vvvec = vector<vector<vector<T>>>; template <typename T> using p_queue = priority_queue<T>; template <typename T> using rp_queue = priority_queue<T, vec<T>, greater<T>>; 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<type>::max() #define MIN(type) numeric_limits<type>::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<ll>::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 <class T> concept addable = requires(T a, T b) { { a + b } -> convertible_to<T>; }; #line 5 "common/util.hpp" // --- Utils --- // 二分探索 template <typename T> inline T bin_search(T ok, T ng, const function<bool(T)> 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<void(vec<int> &)> f) { vec<int> 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<void(int)> f) { rep(i, 1LL << n) f(i); } // 配列 to string template <typename T> inline string join(const vec<T> &v, string sep = " ") { string res = ""; rep(i, v.size()) res += to_string(v[i]) + (i == v.size() - 1 ? "" : sep); return res; } template <typename T> inline void join_out(ostream &os, const vec<T> &v, string sep = " ", string end = "\n") { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? end : sep); } template <typename T> inline void transform(vec<T> &src, function<void(T &)> 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<ll> &v) { return accumulate(all(v), 0LL); } template <addable T> T sum(const vec<T> &v) { return accumulate(all(v), T()); } // 可変引数min template <class... T> auto min(T... a) { return min(initializer_list<common_type_t<T...>>{a...}); } // 可変引数max template <class... T> auto max(T... a) { return max(initializer_list<common_type_t<T...>>{a...}); } template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template <class T> 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 <typename T> struct vec_accumulate : public vec<T> { explicit vec_accumulate(vec<T> &v) : vec<T>(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 <typename T> inline void unique_erase(vec<T> &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.hpp" #line 4 "datastructure/rbst.hpp" template<typename T> struct RBST { private: /// 乱数シード生成器 random_device rd; /// 乱数生成器 mt19937 mt; /// 単位元 T e; /// 演算 function<T(T,T)> 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<T(T,T)> 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<node_t*, node_t*> 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<typename T> struct RBSTMultiSet : public RBST<T> { private: using node_t = typename RBST<T>::node_t; public: inline RBSTMultiSet(): RBST<T>(0, [](T a, T b){return a;}) {} inline size_t lower_bound(const node_t* const t, T val) const { 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); } inline size_t lower_bound(const T val) const { return lower_bound(this->root, val); } inline size_t upper_bound(const node_t* const t, const T val) const { 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); } inline size_t upper_bound(const T val) const { return upper_bound(this->root, val); } inline void insert(const T val) { this->insert_at(lower_bound(val), val); } inline size_t count(const T val) const { return upper_bound(val) - lower_bound(val); } inline bool contains(const T val) const { int idx = lower_bound(val); return idx < this->root->size && this->get_at(idx)->val == val; } inline void erase(const T val) { int idx = lower_bound(val); if(idx < this->root->size && this->get_at(idx)->val == val) { this->erase_at(idx); } } }; template<typename T> struct RBSTSet : public RBSTMultiSet<T> { public: inline RBSTSet(): RBSTMultiSet<T>() {} inline void insert(const 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<int> 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); } } }