結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
![]() |
提出日時 | 2019-06-26 23:59:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 770 ms / 3,000 ms |
コード長 | 2,471 bytes |
コンパイル時間 | 1,752 ms |
コンパイル使用メモリ | 171,984 KB |
実行使用メモリ | 370,560 KB |
最終ジャッジ日時 | 2024-06-26 07:22:22 |
合計ジャッジ時間 | 12,277 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include<bits/stdc++.h> #define debug(x) cerr << #x << ": " << x << endl #define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << endl using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<ll> vll; const ll INF = LLONG_MAX/2; const ll MOD = 1e9+7; const double EPS=1e-12; template<typename KEYTYPE = unsigned long long, int B = 64> class BinaryTrie { struct node { int cnt; KEYTYPE lazy; node *ch[2]; node() : cnt(0), lazy(0), ch{ nullptr, nullptr } {} }; node* insert_node(node* t, KEYTYPE key, int b = B - 1) { if (!t) t = new node; t->cnt += 1; if (b < 0) return t; push(t, b); bool f = (key >> (KEYTYPE)b) & (KEYTYPE)1; t->ch[f] = insert_node(t->ch[f], key, b - 1); return t; } node* erase_node(node* t, KEYTYPE key, int b = B - 1) { assert(t); t->cnt -= 1; if (t->cnt == 0) return nullptr; if (b < 0) return t; push(t, b); bool f = (key >> (KEYTYPE)b) & (KEYTYPE)1; t->ch[f] = erase_node(t->ch[f], key, b - 1); return t; } //[ void push(node* t, int b) { if ((t->lazy >> (KEYTYPE)b) & (KEYTYPE)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; } KEYTYPE get(node* t, int k, int b = B - 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) | ((KEYTYPE)1 << (KEYTYPE)b); } //] node *root; public: BinaryTrie() : root(nullptr) {} void insert(KEYTYPE key) { root = insert_node(root, key); } void erase(KEYTYPE key) { root = erase_node(root, key); } //[ int size() const { return root ? root->cnt : 0; } KEYTYPE kth_element(int k) { assert(0 <= k && k < size()); return get(root, k); } //] }; signed main(){ cin.tie(0); ios::sync_with_stdio(false); ll Q,K;cin>>Q>>K;K--; BinaryTrie<> S; for(ll q=0;q<Q;q++){ ll op;cin>>op; if(op&1){ ll v;cin>>v; S.insert(v); }else{ ll ans=-1; if(S.size()>K){ ans = S.kth_element(K); S.erase(ans); } cout<<ans<<endl; } } return 0; }