結果

問題 No.649 ここでちょっとQK！
ユーザー Imperi_NightImperi_Night
提出日時 2019-12-11 04:19:33
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 652 ms / 3,000 ms
コード長 5,463 bytes
コンパイル時間 1,609 ms
コンパイル使用メモリ 131,756 KB
実行使用メモリ 19,020 KB
最終ジャッジ日時 2023-09-06 11:55:37
合計ジャッジ時間 11,040 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 26 ms
4,380 KB
testcase_04 AC 238 ms
19,016 KB
testcase_05 AC 259 ms
19,020 KB
testcase_06 AC 243 ms
18,960 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 272 ms
9,796 KB
testcase_13 AC 266 ms
9,600 KB
testcase_14 AC 262 ms
9,600 KB
testcase_15 AC 289 ms
9,912 KB
testcase_16 AC 268 ms
10,352 KB
testcase_17 AC 311 ms
10,756 KB
testcase_18 AC 346 ms
11,460 KB
testcase_19 AC 386 ms
12,200 KB
testcase_20 AC 421 ms
12,840 KB
testcase_21 AC 479 ms
13,160 KB
testcase_22 AC 497 ms
13,964 KB
testcase_23 AC 532 ms
14,424 KB
testcase_24 AC 571 ms
15,144 KB
testcase_25 AC 614 ms
15,716 KB
testcase_26 AC 652 ms
16,352 KB
testcase_27 AC 3 ms
4,376 KB
testcase_28 AC 2 ms
4,376 KB
testcase_29 AC 3 ms
4,376 KB
testcase_30 AC 272 ms
9,584 KB
testcase_31 AC 268 ms
10,104 KB
testcase_32 AC 1 ms
4,376 KB
testcase_33 AC 2 ms
4,380 KB
testcase_34 AC 1 ms
4,380 KB
testcase_35 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include <limits>
#include "limits.h"
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " <<"LINE:"<<__LINE__<<"  "<< #i <<":"<< i << std::endl

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }
 
  long long x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P = std::pair<ll, ll>;

//RBST merge/split based 
// multiset
template<typename T>
class RBST{
  private:

  class Xorshift{
    private:
    unsigned int x,y,z,w;

    public:
    Xorshift():x(123456789),y(362436069),z(521288629),w(88675123){}

    unsigned int operator() () {
      unsigned int t=(x^(x<<11));
      x=y;y=z;z=w;
      return w=(w^(w>>19))^(t^(t>>8));
    }
  };

  Xorshift rnd;

  class Node;

  using node_ptr=std::shared_ptr<Node>;
  using F=std::function<bool(T,T)>;

  struct Node{
    node_ptr left,right;
    T val;
    int cnt;
    Node(T val_):val(val_),cnt(1),left(),right(){}
  };

  node_ptr root;
  F comp,equal;

  int count(node_ptr t){return t?t->cnt:0;}

  node_ptr update(node_ptr t){
    if(!t)return t;
    t->cnt=count(t->left)+count(t->right)+1;
    return t;
  }

  node_ptr merge(node_ptr l,node_ptr r){
    if(!l||!r)return l?l:r;

    if(rnd()%(count(l)+count(r))<count(l)){
      l->right=merge(l->right,r);
      return update(l);
    }else{
      r->left=merge(l,r->left);
      return update(r);
    }
  }

  std::pair<node_ptr,node_ptr> split(node_ptr t,int k){
    if(!t)return std::make_pair(t,t);

    if(k<=count(t->left)){
      auto temp=split(t->left,k);
      t->left=temp.second;
      return std::make_pair(temp.first,update(t));
    }else{
      auto temp=split(t->right,k-count(t->left)-1);
      t->right=temp.first;
      return std::make_pair(update(t),temp.second);
    }
  }

  bool find(node_ptr& t,T key){
    if(!t)return false;
    if(equal(t->val,key))return true;

    if(comp(key,t->val))return find(t->left,key);
    else return find(t->right,key);
  }

  int lower_bound(node_ptr& t,T key){
    if(!t)return 0; 

    if(comp(key,t->val)||equal(key,t->val))return lower_bound(t->left,key);
    else return lower_bound(t->right,key)+count(t->left)+1;
  }

  int upper_bound(node_ptr& t,T key){
    if(!t)return 0;
    if(comp(key,t->val))return upper_bound(t->left,key);
    else return upper_bound(t->right,key)+count(t->left)+1;
  }

  void insert(node_ptr& t,node_ptr newnode,int k){
    auto temp=split(t,k);
    t=merge(merge(temp.first,newnode),temp.second);
  }

  void erase(node_ptr& t,int k){
    auto temp=split(t,k+1);
    auto temp2=split(temp.first,k);
    t=merge(temp2.first,temp.second);
  }

  T topk(node_ptr& t,int k){
    if(count(t->left)==k)return t->val;
    if(k<count(t->left))return topk(t->left,k);
    else return topk(t->right,k-count(t->left)-1);
  }

  void build(node_ptr& t,const std::vector<T>& val_,int l,int r){
    if(l==r){
      t=nullptr;
      return;
    }
    if(r==l+1){
      t=std::make_shared<Node>(val_[l]);
      return;
    }

    int mid=l+(r-l)/2;
    t=std::make_shared<Node>(val_[mid]);
    build(t->left,val_,l,mid);
    build(t->right,val_,mid+1,r);
    update(t);
  }

  public:

  RBST(F comp_=[](T a,T b){return a<b;},F equal_=[](T a,T b){return a==b;}):comp(comp_),equal(equal_),root(){};

  void build(const std::vector<T>& val_){
    build(root,val_,0,val_.size());
  }

  int size(){return count(root);}

  bool find(T key){return find(root,key);}

  int count(T key){return upper_bound(root,key)-lower_bound(root,key);}

  int lower_bound(T key){return lower_bound(root,key);}

  int upper_bound(T key){return upper_bound(root,key);}

  void insert(T key){
    insert(root,std::make_shared<Node>(key),lower_bound(root,key));
  }

  void erase(T key){
    if(count(key)==0)return;
    erase(root,lower_bound(root,key));
  }

  T topk(int k){return topk(root,k);}
};

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  RBST<ll> set;

  ll q,k;
  std::cin>>q>>k;

  rep(_,0,q){
    ll t;
    std::cin>>t;

    if(t==1){
      ll v;
      std::cin>>v;

      set.insert(v);
    }else{
      if(set.size()<k){
        std::cout<<-1<<"\n";
      }else{
        ll ans=set.topk(k-1);
        set.erase(ans);
        std::cout<<ans<<"\n";
      }
    }
  }

  return 0;
}
0