結果
問題 | No.649 ここでちょっとQK! |
ユーザー | nok0 |
提出日時 | 2020-12-20 23:39:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 198 ms / 3,000 ms |
コード長 | 3,328 bytes |
コンパイル時間 | 2,251 ms |
コンパイル使用メモリ | 206,908 KB |
実行使用メモリ | 13,180 KB |
最終ジャッジ日時 | 2023-10-21 11:16:22 |
合計ジャッジ時間 | 6,386 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 24 ms
4,348 KB |
testcase_04 | AC | 84 ms
13,180 KB |
testcase_05 | AC | 85 ms
13,180 KB |
testcase_06 | AC | 86 ms
13,180 KB |
testcase_07 | AC | 2 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 2 ms
4,348 KB |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | AC | 2 ms
4,348 KB |
testcase_12 | AC | 72 ms
8,028 KB |
testcase_13 | AC | 72 ms
8,028 KB |
testcase_14 | AC | 70 ms
8,012 KB |
testcase_15 | AC | 74 ms
8,032 KB |
testcase_16 | AC | 71 ms
8,028 KB |
testcase_17 | AC | 82 ms
8,448 KB |
testcase_18 | AC | 93 ms
8,872 KB |
testcase_19 | AC | 103 ms
9,280 KB |
testcase_20 | AC | 114 ms
9,712 KB |
testcase_21 | AC | 133 ms
10,132 KB |
testcase_22 | AC | 143 ms
10,556 KB |
testcase_23 | AC | 150 ms
10,980 KB |
testcase_24 | AC | 167 ms
11,404 KB |
testcase_25 | AC | 179 ms
11,824 KB |
testcase_26 | AC | 198 ms
12,240 KB |
testcase_27 | AC | 2 ms
4,348 KB |
testcase_28 | AC | 3 ms
4,348 KB |
testcase_29 | AC | 2 ms
4,348 KB |
testcase_30 | AC | 64 ms
8,024 KB |
testcase_31 | AC | 68 ms
8,020 KB |
testcase_32 | AC | 2 ms
4,348 KB |
testcase_33 | AC | 2 ms
4,348 KB |
testcase_34 | AC | 2 ms
4,348 KB |
testcase_35 | AC | 2 ms
4,348 KB |
ソースコード
#include <bits/stdc++.h> template <typename T> struct treap { private: struct xorshift { using u32 = uint32_t; u32 x = 123456789, y = 362436069, z = 521288629, w = 88675123; xorshift(u32 seed = 0) { z ^= seed; } u32 operator()() { u32 t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } }; xorshift rnd; struct Node { T key; int pri, cnt; Node *l, *r; Node(T key_, int pri_) : key(key_), pri(pri_), cnt(1), l(nullptr), r(nullptr) {} } *root = nullptr; using Tree = Node *; int count(Tree t) { return t ? t->cnt : 0; } void update_cnt(Tree &t) { if(t) t->cnt = 1 + count(t->l) + count(t->r); } void split(Tree t, T key, Tree &l, Tree &r) { if(!t) l = r = nullptr; else if(key < t->key) split(t->l, key, l, t->l), r = t, update_cnt(r); else split(t->r, key, t->r, r), l = t, update_cnt(l); } void merge(Tree &t, Tree l, Tree r) { if(!l or !r) t = l ? l : r; else if(l->pri > r->pri) merge(l->r, l->r, r), t = l, update_cnt(t); else merge(r->l, l, r->l), t = r, update_cnt(t); } void insert(Tree &t, Tree item) { if(!t) t = item; else if(item->pri > t->pri) split(t, item->key, item->l, item->r), t = item, update_cnt(t); else insert(item->key < t->key ? t->l : t->r, item), update_cnt(t); } void erase(Tree &t, T key) { if(t->key == key) merge(t, t->l, t->r); else erase(key < t->key ? t->l : t->r, key), update_cnt(t); } bool find(Tree &t, T key) { if(!t) return false; else if(t->key == key) return true; else return find(key < t->key ? t->l : t->r, key); } Tree lower_bound(Tree &t, T key) { if(!t) return nullptr; else if(t->key >= key) { Tree res = lower_bound(t->l, key); return res == nullptr ? t : res; } else return lower_bound(t->r, key); } Tree upper_bound(Tree &t, T key) { if(!t) return nullptr; else if(t->key > key) { Tree res = upper_bound(t->l, key); return res == nullptr ? t : res; } else return upper_bound(t->r, key); } Tree kth_element(Tree &t, int cnt) { if(!t) return nullptr; int sum = count(t->l) + 1; return (cnt < sum ? kth_element(t->l, cnt) : (sum == cnt ? t : kth_element(t->r, cnt - sum))); } void dump(Tree &t) { if(!t) return; dump(t->l); std::cout << t->key << " "; dump(t->r); } public: void insert(const T key) { // if it is set, use ↓ // if(find(key)) return; insert(root, new Node(key, rnd())); } void erase(const T key) { erase(root, key); } bool find(const T key) { return find(root, key); } Tree lower_bound(const T key) { return lower_bound(root, key); } Tree upper_bound(const T key) { return upper_bound(root, key); } //0_indexed T kth_element(const int cnt) { assert(root and 0 <= cnt and cnt < root->cnt); return kth_element(root, cnt + 1)->key; } int size() { return root ? root->cnt : 0; } void dump() { dump(root); std::cout << "\n"; } }; int q, k, type; long long x; int main() { scanf("%d%d", &q, &k); treap<long long> set; while(q--) { scanf("%d", &type); if(type == 1) { scanf("%lld", &x); set.insert(x); } if(type == 2) { if(set.size() < k) puts("-1"); else { long long res = set.kth_element(k - 1); printf("%lld\n", res); set.erase(res); } } } return 0; }