結果

問題 No.649 ここでちょっとQK！
ユーザー kusaf_kusaf_
提出日時 2024-11-03 02:46:06
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 27 ms
6,816 KB
testcase_04 AC 130 ms
22,144 KB
testcase_05 AC 130 ms
22,144 KB
testcase_06 AC 101 ms
6,820 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 AC 370 ms
195,200 KB
testcase_13 AC 342 ms
195,328 KB
testcase_14 AC 326 ms
180,736 KB
testcase_15 AC 394 ms
192,128 KB
testcase_16 AC 327 ms
191,232 KB
testcase_17 AC 367 ms
209,280 KB
testcase_18 AC 410 ms
227,456 KB
testcase_19 AC 457 ms
244,992 KB
testcase_20 AC 503 ms
263,296 KB
testcase_21 AC 554 ms
281,344 KB
testcase_22 AC 559 ms
299,264 KB
testcase_23 AC 612 ms
317,056 KB
testcase_24 AC 655 ms
335,104 KB
testcase_25 AC 690 ms
352,768 KB
testcase_26 AC 730 ms
370,432 KB
testcase_27 AC 2 ms
6,816 KB
testcase_28 AC 2 ms
6,820 KB
testcase_29 AC 2 ms
6,820 KB
testcase_30 AC 85 ms
13,824 KB
testcase_31 AC 69 ms
10,624 KB
testcase_32 AC 2 ms
6,816 KB
testcase_33 AC 2 ms
6,816 KB
testcase_34 AC 2 ms
6,816 KB
testcase_35 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);
      }
    }
  }
}
0