結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー tonegawa
提出日時 2020-10-02 04:24:55
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 505 ms / 3,000 ms
コード長 7,953 bytes
コンパイル時間 2,966 ms
コンパイル使用メモリ 145,092 KB
最終ジャッジ日時 2025-01-14 23:53:49
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

const long long ERROR = (1ULL<<63) - 1;
template<typename E>
struct BinaryTrieMultiset64{
private:
  struct node{
    node* ch[2];
    E cnt;
    node(): ch{nullptr, nullptr}, cnt(0){}
  };
  const uint64_t UINTMAX = ((1ULL<<63) - 1) + (1ULL<<63);
  node* root = new node();

  inline bool inner_insert(uint64_t x, E add = 1){
    int Kbit = 63;
    node* cur = root;
    while((Kbit+1)){
      bool nxt = (x>>Kbit)&1;
      if(!cur->ch[nxt]){
        auto to = new node();
        cur->ch[nxt] = to;
      }
      cur->cnt += add;
      cur = cur->ch[nxt];
      Kbit--;
    }
    cur->cnt += add;
    return true;
  }

  inline E inner_erase(node* cur, int Kbit, uint64_t x, E k = -1){
    if(Kbit==-1){
      E erase_num = (k==-1?cur->cnt:std::min(cur->cnt, k));
      cur->cnt -= erase_num;
      return erase_num;
    }
    bool nxt = (x>>Kbit)&1;
    if(!cur->ch[nxt]||cur->ch[nxt]->cnt==0) return false;
    E erase_num = inner_erase(cur->ch[nxt], Kbit-1, x, k);
    if(erase_num){
      cur->cnt -= erase_num;
      return true;
    }
    return false;
  }

  inline E inner_find(node* cur, int Kbit, uint64_t x){
    if(Kbit==-1) return cur->cnt;
    bool nxt = (x>>Kbit)&1;
    if(!cur->ch[nxt]||cur->ch[nxt]->cnt==0) return 0;
    return inner_find(cur->ch[nxt], Kbit-1, x);
  }

  inline uint64_t inner_max(){
    node* cur = root;
    uint64_t ret = 0;
    int Kbit = 63;
    while(cur->ch[0]||cur->ch[1]){
      if(cur->ch[1]) ret |= (1ULL<<Kbit), cur = cur->ch[1];
      else cur = cur->ch[0];
      Kbit--;
    }
    return ret;
  }

  inline uint64_t inner_min(){
    node* cur = root;
    uint64_t ret = 0;
    int Kbit = 63;
    while(cur->ch[0]||cur->ch[1]){
      if(cur->ch[0]) cur = cur->ch[0];
      else ret |= (1ULL << Kbit), cur = cur->ch[1];
      Kbit--;
    }
    return ret;
  }

  inline uint64_t inner_upper_bound(uint64_t x){
    int Kbit = 63;
    node* lca = nullptr;//最も深い位置で右に別れたノード
    int lcabit;
    uint64_t ret = 0;
    uint64_t lcaret = 0;

    node* cur = root;
    while(Kbit){
      bool nxt = (x>>Kbit)&1;
      if(nxt){
        if(!cur->ch[1]||cur->ch[1]->cnt==0) break;
        else cur = cur->ch[1];
        ret |= (1ULL<<Kbit);
      }else{
        if(cur->ch[1]&&cur->ch[1]->cnt) {
          lca = cur->ch[1];
          lcabit = Kbit - 1;
          lcaret = ret | (1ULL<<Kbit);
        }
        cur = cur->ch[0];
      }
      Kbit--;
    }
    if(!(x&1)&&cur->ch[1]&&cur->ch[1]->cnt) return ret + 1;

    if(!lca) return UINTMAX;
    cur = lca;
    while(lcabit){
      if(cur->ch[0]&&cur->ch[0]->cnt) cur = cur->ch[0];
      else{
        lcaret |= (1ULL<<lcabit);
        cur = cur->ch[1];
      }
      lcabit--;
    }
    if(!cur->ch[0]||cur->ch[0]->cnt==0) lcaret++;
    return lcaret;
  }

  inline uint64_t inner_reverse_upper_bound(uint64_t x){
    int Kbit = 63;
    node* lca = nullptr;//最も深い位置で右に別れたノード
    int lcabit;
    uint64_t ret = 0;
    uint64_t lcaret = 0;

    node* cur = root;
    while(Kbit){
      bool nxt = (x>>Kbit)&1;

      if(!nxt){
        if(!cur->ch[0]||cur->ch[0]->cnt==0) break;
        else cur = cur->ch[0];
      }else{
        if(cur->ch[0]&&cur->ch[0]->cnt) {
          lca = cur->ch[0];
          lcabit = Kbit - 1;
          lcaret = ret;
        }
        cur = cur->ch[1];
        ret |= (1ULL<<Kbit);
      }
      Kbit--;
    }
    if((x&1)&&cur->ch[0]&&cur->ch[0]->cnt) return ret;
    if(!lca) return UINTMAX;

    cur = lca;
    while(lcabit){
      if(cur->ch[1]&&cur->ch[1]->cnt) {
        cur = cur->ch[1];
        lcaret |= (1ULL<<lcabit);
      }else{
        cur = cur->ch[0];
      }
      lcabit--;
    }
    if(cur->ch[1]&&cur->ch[1]->cnt) lcaret++;
    return lcaret;
  }

  inline uint64_t inner_kth_element(E k){
    int Kbit = 63;
    node* cur = root;
    uint64_t ret = 0;
    while(Kbit){
      if(!cur->ch[0]){
        ret |= (1ULL<<Kbit);
        cur = cur->ch[1];
      }else if(cur->ch[0]->cnt>k){
        cur = cur->ch[0];
      }else{
        k -= cur->ch[0]->cnt;
        ret |= (1ULL<<Kbit);
        cur = cur->ch[1];
      }
      Kbit--;
    }
    if(!cur->ch[0]||cur->ch[0]->cnt<=k) ret++;
    return ret;
  }

  inline E inner_under_count(uint64_t x){
    int Kbit = 63;
    node* cur = root;
    E ret = 0;
    while(Kbit){
      bool nxt = (x>>Kbit)&1;
      if(nxt){
        if(cur->ch[0]) ret += cur->ch[0]->cnt;
        if(!cur->ch[1]||cur->ch[1]->cnt==0) return ret;
        else cur = cur->ch[1];
      }else{
        if(!cur->ch[0]||cur->ch[0]->cnt==0) return ret;
        else cur = cur->ch[0];
      }
      Kbit--;
    }
    if(x&1 && cur->ch[0]) ret += cur->ch[0]->cnt;
    return ret;
  }

public:
  //templateのEはsizeの型(要素の和の最大数)
  inline E size(){
    return root->cnt;
  }
  //1個挿入
  inline bool insert(long long x){
    if(x==ERROR) return false;
    uint64_t y = (uint64_t)(x + (1ULL<<63));
    return inner_insert(y);
  }
  //全て消してその個数を返す
  inline E erase(long long x){
    if(x==ERROR) return 0;
    uint64_t y = (uint64_t)(x + (1ULL<<63));
    return inner_erase(root, 63, y);
  }
  //k個挿入
  inline bool insert_k(long long x, E k){
    if(x==ERROR) return false;
    uint64_t y = (uint64_t)(x + (1ULL<<63));
    return inner_insert(y, k);
  }
  //k個削除を試みて消した個数を返す
  inline E erase_k(long long x, E k){
    if(x==ERROR) return 0;
    uint64_t y = (uint64_t)(x + (1ULL<<63));
    return inner_erase(root, 63, y, k);
  }
  //xの個数を返す, multisetのcountを兼ねている
  inline E find(long long x){
    if(x==ERROR) return 0;
    uint64_t y = (uint64_t)(x + (1ULL<<63));
    return inner_find(root, 63, y);
  }
  inline long long max(){
    if(size()==0) return ERROR;
    return (long long)inner_max() - (1ULL<<63);
  }
  inline long long min(){
    if(size()==0) return ERROR;
    return (long long)inner_min() - (1ULL<<63);
  }
  inline long long lower_bound(long long x){
    uint64_t y = (uint64_t)(x + (1ULL<<63) - 1);
    return (long long)inner_upper_bound(y) - (1LL<<63);
  }
  inline long long upper_bound(long long x){
    if(x==ERROR) return ERROR;
    uint64_t y = (uint64_t)(x + (1ULL<<63));
    return (long long)inner_upper_bound(y) - (1LL<<63);
  }
  inline long long reverse_upper_bound(long long x){
    uint64_t y = (uint64_t)(x + (1ULL<<63));
    return (long long)inner_reverse_upper_bound(y) - (1LL<<63);
  }
  inline long long reverse_lower_bound(long long x){
    if(x==ERROR) return ERROR;
    uint64_t y = (uint64_t)(x + (1ULL<<63) + 1);
    return (long long)inner_reverse_upper_bound(y) - (1LL<<63);
  }
  //k番目の値を返す(0-indexed) O(logN)
  inline long long kth_element(E k){
    if(size()<=k) return ERROR;
    return (long long)inner_kth_element(k) - (1LL<<63);
  }
  //x未満の値を数える O(logN)
  inline E under_count(long long x){
    uint64_t y = (uint64_t)(x + (1ULL<<63));
    return inner_under_count(y);
  }
};

int main(){
  BinaryTrieMultiset64<int> st;
  int q, k;scanf("%d %d", &q, &k);
  for(int i=0;i<q;i++){
    ll x;scanf("%lld", &x);
    if(x==1){
      ll y;scanf("%lld", &y);
      st.insert(y);
    }else{
      ll t = st.kth_element(k-1);
      if(t==ERROR) printf("%d\n", -1);
      else{
        st.erase_k(t, 1);
        printf("%lld\n", t);
      }
    }
  }
}
0