結果
問題 | No.649 ここでちょっとQK! |
ユーザー | kusaf_ |
提出日時 | 2024-11-03 02:46:06 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 730 ms / 3,000 ms |
コード長 | 3,342 bytes |
コンパイル時間 | 3,231 ms |
コンパイル使用メモリ | 250,984 KB |
実行使用メモリ | 370,432 KB |
最終ジャッジ日時 | 2024-11-03 02:46:22 |
合計ジャッジ時間 | 15,343 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;template<int MAX_LOG = 32, typename T = int> struct BinaryTrie {private:struct node {int cnt;T lazy;node *ch[2];node(): cnt(0), lazy(0), ch{nullptr, nullptr} {}};void push(node *t, int b) {if((t->lazy >> (T)b) & (T)1) { swap(t->ch[0], t->ch[1]); }if(t->ch[0]) { t->ch[0]->lazy ^= t->lazy; }if(t->ch[1]) { t->ch[1]->lazy ^= t->lazy; }t->lazy = 0;}node *add(node *t, T val, int b = MAX_LOG - 1) {if(!t) { t = new node; }t->cnt += 1;if(b < 0) { return t; }push(t, b);bool f = (val >> (T)b) & (T)1;t->ch[f] = add(t->ch[f], val, b - 1);return t;}node *sub(node *t, T val, int b = MAX_LOG - 1) {assert(t);t->cnt -= 1;if(t->cnt == 0) { return nullptr; }if(b < 0) { return t; }push(t, b);bool f = (val >> (T)b) & (T)1;t->ch[f] = sub(t->ch[f], val, b - 1);return t;}T get_min(node *t, T val, int b = MAX_LOG - 1) {assert(t);if(b < 0) { return 0; }push(t, b);bool f = (val >> (T)b) & (T)1;f ^= !t->ch[f];return get_min(t->ch[f], val, b - 1) | ((T)f << (T)b);}T get(node *t, int k, int b = MAX_LOG - 1) {if(b < 0) { return 0; }push(t, b);int m = t->ch[0] ? t->ch[0]->cnt : 0;return k < m ? get(t->ch[0], k, b - 1) : get(t->ch[1], k - m, b - 1) | ((T)1 << (T)b);}int count_lower(node *t, T val, int b = MAX_LOG - 1) {if(!t || b < 0) { return 0; }push(t, b);bool f = (val >> (T)b) & (T)1;return (f && t->ch[0] ? t->ch[0]->cnt : 0) + count_lower(t->ch[f], val, b - 1);}node *root;public:BinaryTrie(): root(nullptr) {}int size() const { return root ? root->cnt : 0; }bool empty() const { return !root; }void insert(T val) { root = add(root, val); }void erase(T val) {if(!count(val)) { return; }root = sub(root, val);}void xor_all(T val) {if(root) { root->lazy ^= val; }}T max_element(T xor_val = 0) {xor_all(xor_val);T r = get_min(root, -1);xor_all(xor_val);return r;}T min_element(T xor_val = 0) {xor_all(xor_val);T r = get_min(root, 0);xor_all(xor_val);return r;}T kth_smallest(int k, T xor_val = 0) {assert(0 <= k && k < size());xor_all(xor_val);T r = get(root, k);xor_all(xor_val);return r;}int lower_bound(T val, T xor_val = 0) {xor_all(xor_val);int r = count_lower(root, val);xor_all(xor_val);return r;}int upper_bound(T val, T xor_val = 0) {xor_all(xor_val);int r = count_lower(root, val + 1);xor_all(xor_val);return r;}int count(T val) {if(!root) { return 0; }node *t = root;for(int i = MAX_LOG - 1; i >= 0; i--) {push(t, i);t = t->ch[(val >> (T)i) & (T)1];if(!t) { return 0; }}return t->cnt;}};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);ll Q, K;cin >> Q >> K;K--;BinaryTrie<62, ll> B;while(Q--) {ll type;cin >> type;if(type == 1) {ll v;cin >> v;B.insert(v);}else {if(B.size() <= K) { cout << -1 << "\n"; }else {ll ans = B.kth_smallest(K);cout << ans << "\n";B.erase(ans);}}}}