結果

問題 No.649 ここでちょっとQK！
ユーザー tonegawatonegawa
提出日時 2020-10-02 04:24:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 593 ms / 3,000 ms
コード長 7,953 bytes
コンパイル時間 1,257 ms
コンパイル使用メモリ 117,364 KB
実行使用メモリ 247,720 KB
最終ジャッジ日時 2023-09-22 01:47:46
合計ジャッジ時間 11,595 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 33 ms
4,376 KB
testcase_04 AC 100 ms
16,252 KB
testcase_05 AC 99 ms
16,160 KB
testcase_06 AC 75 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 295 ms
128,680 KB
testcase_13 AC 292 ms
128,616 KB
testcase_14 AC 270 ms
118,952 KB
testcase_15 AC 288 ms
128,988 KB
testcase_16 AC 283 ms
128,648 KB
testcase_17 AC 311 ms
140,728 KB
testcase_18 AC 341 ms
152,944 KB
testcase_19 AC 378 ms
164,368 KB
testcase_20 AC 402 ms
176,672 KB
testcase_21 AC 442 ms
188,504 KB
testcase_22 AC 463 ms
200,432 KB
testcase_23 AC 514 ms
212,412 KB
testcase_24 AC 536 ms
224,348 KB
testcase_25 AC 573 ms
236,040 KB
testcase_26 AC 593 ms
247,720 KB
testcase_27 AC 3 ms
4,380 KB
testcase_28 AC 2 ms
4,380 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 57 ms
8,176 KB
testcase_31 AC 56 ms
8,164 KB
testcase_32 AC 2 ms
4,380 KB
testcase_33 AC 2 ms
4,384 KB
testcase_34 AC 1 ms
4,380 KB
testcase_35 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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