結果

問題 No.649 ここでちょっとQK！
ユーザー tnakao0123tnakao0123
提出日時 2018-02-16 09:28:39
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 197 ms / 3,000 ms
コード長 4,203 bytes
コンパイル時間 1,040 ms
コンパイル使用メモリ 97,088 KB
実行使用メモリ 11,376 KB
最終ジャッジ日時 2023-08-30 02:37:29
合計ジャッジ時間 8,074 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 22 ms
4,376 KB
testcase_04 AC 77 ms
11,360 KB
testcase_05 AC 78 ms
11,316 KB
testcase_06 AC 77 ms
11,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 76 ms
7,584 KB
testcase_13 AC 75 ms
7,620 KB
testcase_14 AC 75 ms
7,644 KB
testcase_15 AC 78 ms
7,576 KB
testcase_16 AC 74 ms
7,576 KB
testcase_17 AC 89 ms
7,572 KB
testcase_18 AC 95 ms
9,616 KB
testcase_19 AC 105 ms
9,688 KB
testcase_20 AC 117 ms
9,688 KB
testcase_21 AC 126 ms
9,720 KB
testcase_22 AC 143 ms
9,700 KB
testcase_23 AC 149 ms
9,692 KB
testcase_24 AC 163 ms
9,892 KB
testcase_25 AC 174 ms
10,296 KB
testcase_26 AC 197 ms
10,528 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 2 ms
4,376 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 68 ms
7,644 KB
testcase_31 AC 66 ms
7,596 KB
testcase_32 AC 1 ms
4,376 KB
testcase_33 AC 1 ms
4,380 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 649.cc: No.649 ここでちょっとQK! - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 200000;
const long long LINF = 1LL << 62;

/* typedef */

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

template <typename T, const int BUFSIZE>
struct Treap {
  struct Node {
    T key, minkey;
    int fix, size;
    Node *left, *right;

    void print(int k) {
      printf("%d: key=%lld, minkey=%lld, fix=%d, size=%d\n",
	     k, key, minkey, fix, size);
    }
    void print() { print(0); }
  };
  typedef Node *node;

  node root, nullnode, buf;
  Node buf0[BUFSIZE], buf1;

  const T TINF;
  
  Treap(T tinf): TINF(tinf) {
    nullnode = &buf1;
    nullnode->left = nullnode->right = nullnode;
    nullnode->key = nullnode->minkey = TINF;
    nullnode->fix = nullnode->size = 0;
    clear();
    srand(time(NULL));
  }

  void clear() { buf = buf0; root = nullnode; }
  
  int size() { return root->size; }

  void update(node& t) {
    t->size = 1 + t->left->size + t->right->size;
    t->minkey = t->key;
    if (t->minkey > t->left->minkey) t->minkey = t->left->minkey;
    if (t->minkey > t->right->minkey) t->minkey = t->right->minkey;
  }

  node gen_node(T x) {
    node t = buf++;
    t->left = t->right = nullnode;
    t->key = t->minkey = x;
    t->fix = rand();
    t->size = 1;
    return t;
  }
  
  void rot_l(node& k1) {
    node k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    update(k1);
    update(k2);
    k1 = k2;
  }

  void rot_r(node& k1) {
    node k2 = k1->left;
    k1->left = k2->right;
    k2->right = k1;
    update(k1);
    update(k2);
    k1 = k2;
  }

  void insert(node& t, T x) {
    if (t == nullnode)
      t = gen_node(x);
    else {
      if (x <= t->key) {
	insert(t->left, x);
	update(t);
	if (t->left->fix > t->fix) rot_r(t);
      }
      else {
	insert(t->right, x);
	update(t);
	if (t->right->fix > t->fix) rot_l(t);
      }
    }
  }
  void insert(T x) { insert(root, x); }

  void remove_node(node& t) {
    if (t == nullnode) return;
    if (t->left == nullnode || t->right == nullnode) {
      if (t->left == nullnode)
	t = t->right;
      else
	t = t->left;
    }
    else {
      if (t->left->fix < t->right->fix) {
	rot_l(t);
	remove_node(t->left);
	update(t);
      }
      else {
	rot_r(t);
	remove_node(t->right);
	update(t);
      }
    }
  }

  T removeat(node& t, int i) {
    T ret = TINF;

    if (t != nullnode) {
      int lsize = t->left->size;
      if (i == lsize) {
	ret = t->key;
	remove_node(t);
      }
      else if (i < lsize) {
	ret = removeat(t->left, i);
	update(t);
      }
      else {
	ret = removeat(t->right, i - (lsize + 1));
	update(t);
      }
    }

    return ret;
  }
  T removeat(int i) { return removeat(root, i); }
  
  void print(node t, int k, int indent) {
    if (t == nullnode) return;
    if (t != NULL) {
      for (int i = 0; i < indent; i++) cout << "  ";
      t->print(k + t->left->size);
      print(t->left, k, indent + 1);
      print(t->right, k + t->left->size + 1, indent + 1);
    }
  }
  void print() { print(root, 0, 0); }

  void inorder(node t) {
    if (t != nullnode && t != NULL) {
      inorder(t->left);
      cout << t->key << ' ';
      inorder(t->right);
    }
  }
  void inorder() {
    inorder(root);
    cout << endl;
  }
};

/* global variables */

Treap<ll,MAX_N> trp(LINF);

/* subroutines */

/* main */

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  k--;

  int sz = 0;
  for (int i = 0; i < n; i++) {
    int op;
    scanf("%d", &op);

    if (op == 1) { // add
      ll v;
      scanf("%lld", &v);
      trp.insert(v);
      sz++;
      //printf("1 %lld\n", v);
      //trp.inorder();
    }
    else { // remove
      if (sz <= k) puts("-1");
      else {
	ll v = trp.removeat(k);
	sz--;
	printf("%lld\n", v);
      }
    }
  }
  return 0;
}
0