結果

問題 No.649 ここでちょっとQK！
ユーザー hamrayhamray
提出日時 2020-11-13 18:44:06
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 244 ms / 3,000 ms
コード長 5,822 bytes
コンパイル時間 1,621 ms
コンパイル使用メモリ 170,148 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2024-07-22 20:11:43
合計ジャッジ時間 6,063 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 26 ms
5,376 KB
testcase_04 AC 90 ms
12,928 KB
testcase_05 AC 95 ms
12,800 KB
testcase_06 AC 91 ms
12,928 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 104 ms
7,680 KB
testcase_13 AC 103 ms
7,552 KB
testcase_14 AC 100 ms
7,680 KB
testcase_15 AC 109 ms
7,680 KB
testcase_16 AC 101 ms
7,680 KB
testcase_17 AC 116 ms
8,064 KB
testcase_18 AC 128 ms
8,576 KB
testcase_19 AC 143 ms
8,960 KB
testcase_20 AC 154 ms
9,344 KB
testcase_21 AC 167 ms
9,856 KB
testcase_22 AC 183 ms
10,240 KB
testcase_23 AC 198 ms
10,624 KB
testcase_24 AC 218 ms
11,136 KB
testcase_25 AC 229 ms
11,520 KB
testcase_26 AC 244 ms
11,904 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 96 ms
7,680 KB
testcase_31 AC 96 ms
7,552 KB
testcase_32 AC 1 ms
5,376 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace atcoder;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const double pi = 3.141592653589793238462643383279;
using namespace std;
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a) (a).begin(), (a).endf()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a) * (a))
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).endf(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).endf())
#define SORT(c) sort((c).begin(), (c).endf())

//repetition
//------------------------------------------
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define MOD 1000000007

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const double EPS = 1e-4, PI = acos(-1);
//ここから編集    
typedef string::const_iterator State;
template<class T> 
class Treap {
public:
  struct node_t{
    T val, sum;
    node_t *lch, *rch;
    int pri; // 優先度
    int size; // 部分木のサイズ
    node_t(T v, int p) : val(v), pri(p), size(1), sum(v) {
      lch = rch = nullptr;
    }
  };

  node_t *root;
  Treap() : root(nullptr){
    srand(time(NULL));
  }
  using np = node_t*;
  using npp = pair<np, np>;

  int size(np t) {return (t==nullptr)?0:t->size; }/* 平衡二分木のサイズを返す */
  int size() { return (root==nullptr)?0:root->size; }
  T sum(np t){return (t==nullptr)?0:t->sum; }

  np update(np t){
    t->size = size(t->lch) + size(t->rch) + 1;
    t->sum = sum(t->lch) + sum(t->rch) + t->val;
    return t;
  }
  np merge(np l, np r){
    if(l == nullptr || r == nullptr){
      return (l==nullptr)?r:l;
    }
    if(l->pri > r->pri){        //左の部分木の根の方が優先度が高い場合
      l->rch = merge(l->rch, r);
      return update(l);
    }else{                      //右の部分木の根の方が優先度が高い場合
      r->lch = merge(l, r->lch);
      return update(r);
    }
  }
  npp split(np t, int k){ // [0, k), [k, n)
    if(t==nullptr) return make_pair(nullptr, nullptr);

    if(k <= size(t->lch)) {
      npp s = split(t->lch, k);
      t->lch = s.second;
      return make_pair(s.first, update(t));
    }else{
      npp s = split(t->rch, k-size(t->lch) - 1);
      t->rch = s.first;
      return make_pair(update(t), s.second);
    }
  }
  /* キーkが存在するか */
  bool find(T k) { return find(root, k); }
  bool find(np t, T x){
    if(t==nullptr) return false;
    if(t->val==x) return true;
    else if(t->val>x) {
      if(t->lch!=nullptr) return find(t->lch,x);
    }else {
      if(t->rch!=nullptr) return find(t->rch,x);
    }
    return false;
  }


  /* tが根となっている木のk番目に値val, 優先度priのノードを挿入 */
  void kth_insert(int k, T val, int pri) { root = kth_insert(root, k, val, pri);}
  void kth_insert(int k, T val) { root = kth_insert(root, k, val, rand()); }
  np kth_insert(np t, int k, T val, int pri){
    npp s = split(t, k);
    t = merge(s.first, new node_t(val, pri));
    t = merge(t, s.second);
    return update(t);
  }

  /* k番目の要素を削除する */
  void kth_erase(T k) { root = erase(root, k); }
  np erase(np t, int k){
    npp u, v;
    u = split(t, k+1);
    v = split(u.first, k);
    t = merge(v.first, u.second);
    return update(t);
  }

  /* k以上で最小のindex */
  int lower_bound(np t, T val){
    if(t == nullptr) return 0;
    if(val <= t->val) return lower_bound(t->lch, val);
    else return size(t->lch) + lower_bound(t->rch, val) + 1;
  }
  int lower_bound(T val) {
    return lower_bound(root, val);
  }

  /* kより大きい要素で最小のindex */
  int upper_bound(np t, T val){
    if(t == nullptr) return 0;
    if(val >= t->val) return size(t->lch) + upper_bound(t->rch, val) + 1;
    else return upper_bound(t->lch, val);
  }
  int upper_bound(T val){
    return upper_bound(root, val);
  }

  /* 要素valの数をカウント */
  T count(T val){
    return upper_bound(val) - lower_bound(val);
  }

  /* k番目の要素を取得する(0-index) */
  T get(np t, int k){
    if(t == nullptr) return -1;
    if(k == size(t->lch)) return t->val;
    if(k < size(t->lch)) return get(t->lch, k);
    else return get(t->rch, k - size(t->lch) - 1);
  }

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

  /* 値valを挿入する */
  void insert(T val){
    npp sub = split(root, lower_bound(val));
    root = merge(merge(sub.first, new node_t(val, rand())), sub.second);
  }

  /* 値valを削除する */
  void erase(T val){
    if(count(val) == 0) return;
    npp sub = split(root, lower_bound(val));
    root = merge(sub.first, split(sub.second, 1).second);
  }
}; 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    int Q, K; cin >> Q >> K;
    Treap<ll> treap;
    while(Q--){
      int t; cin >> t;
      if(t == 1){
        ll v; cin >> v;
        treap.insert(v);
      }else{
        if(treap.size() < K) cout << -1 << '\n';
        else {
          ll e = treap.get(K-1);
          cout << e << '\n';
          treap.erase(e);
        }
      }
    }
    return 0;
}
0