結果

問題 No.649 ここでちょっとQK！
ユーザー yuppe19 😺yuppe19 😺
提出日時 2019-03-07 15:08:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 352 ms / 3,000 ms
コード長 4,246 bytes
コンパイル時間 757 ms
コンパイル使用メモリ 79,000 KB
実行使用メモリ 14,464 KB
最終ジャッジ日時 2024-06-23 14:50:13
合計ジャッジ時間 6,643 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 25 ms
6,940 KB
testcase_04 AC 134 ms
14,464 KB
testcase_05 AC 158 ms
14,336 KB
testcase_06 AC 139 ms
14,464 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 164 ms
8,448 KB
testcase_13 AC 158 ms
8,320 KB
testcase_14 AC 151 ms
8,448 KB
testcase_15 AC 163 ms
8,320 KB
testcase_16 AC 158 ms
8,448 KB
testcase_17 AC 179 ms
8,960 KB
testcase_18 AC 197 ms
9,472 KB
testcase_19 AC 207 ms
9,856 KB
testcase_20 AC 230 ms
10,496 KB
testcase_21 AC 257 ms
10,880 KB
testcase_22 AC 272 ms
11,520 KB
testcase_23 AC 290 ms
12,032 KB
testcase_24 AC 317 ms
12,288 KB
testcase_25 AC 332 ms
12,800 KB
testcase_26 AC 352 ms
13,440 KB
testcase_27 AC 3 ms
6,940 KB
testcase_28 AC 3 ms
6,940 KB
testcase_29 AC 3 ms
6,944 KB
testcase_30 AC 150 ms
8,448 KB
testcase_31 AC 149 ms
8,448 KB
testcase_32 AC 2 ms
6,940 KB
testcase_33 AC 1 ms
6,940 KB
testcase_34 AC 2 ms
6,944 KB
testcase_35 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
using i64 = int64_t;
using u32 = uint32_t;

u32 uy = u32(time(NULL));
u32 xorshift32() {
  uy ^= uy << 14;
  uy ^= uy >> 13;
  uy ^= uy << 15;
  return uy;
}

template <typename T>
bool __attribute__((noinline)) is_null(T* obj) { return obj == nullptr; }

// RBST (Randomised Binary Search Tree)
template <class T>
struct RBST {
  struct Node { // {{{ Node
    constexpr static T nullval = -1; // valueAt() で不正な場所が指定されたときに返す値.
    T val;
    int treeSize;
    Node *lo, *hi;

    explicit Node(T x) : val(x), treeSize(1), lo(nullptr), hi(nullptr) {}

    int size() {
      if(is_null(this)) { return 0; }
      return treeSize;
    }

    Node* update() {
      treeSize = lo->size() + hi->size() + 1;
      return this;
    }

    static Node* merge(Node *l, Node *r) {
      if(is_null(l)) { return r; }
      if(is_null(r)) { return l; }
      size_t lSize = l->size(),
             rSize = r->size();
      if(xorshift32() % (lSize + rSize) < lSize) {
        l->hi = merge(l->hi, r);
        return l->update();
      } else {
        r->lo = merge(l, r->lo);
        return r->update();
      }
    }

    pair<Node*, Node*> split(int k) { // [0, k), [k, n)
      if(is_null(this)) { return make_pair(nullptr, nullptr); }
      if(k <= lo->size()) {
        auto s = lo->split(k);
        lo = s.second;
        return make_pair(s.first, update());
      } else {
        auto s = hi->split(k - lo->size() - 1);
        hi = s.first;
        return make_pair(update(), s.second);
      }
    }

    int indexOf(T x) {
      if(is_null(this)) { return -1; }
      if(x == this->val) { return lo->size(); }
      if(x <  this->val) {
        return lo->indexOf(x);
      } else {
        return lo->size() + 1 + hi->indexOf(x);
      }
    }

    T valueAt(int pos) {
      if(is_null(this)) { return nullval; }
      int loSize = lo->size();
      if(loSize == pos) { return val; }
      if(loSize > pos) {
        return lo->valueAt(pos);
      } else {
        return hi->valueAt(pos - lo->size() - 1);
      }
    }

    int lowerBound(T x) {
      if(is_null(this)) { return 0; }
      if(x <= this->val) { return lo->lowerBound(x); }
      return hi->lowerBound(x) + lo->size() + 1;
    }

    int upperBound(T x) {
      if(is_null(this)) { return 0; }
      if(x >= this->val) { return lo->size() + 1 + hi->upperBound(x); }
      return lo->upperBound(x);
    }

    int count(T x) {
      return upperBound(x) - lowerBound(x);
    }

    Node* insert(int pos, T x) {
      Node *p = new Node(x);
      auto s = split(pos);
      return merge(merge(s.first, p), s.second);
    }

    Node* insert(T x) {
      return insert(lowerBound(x), x);
    }

    Node* deleteAt(int pos) {
      auto s = split(pos);
      auto t = s.second->split(1);
      t.first = nullptr;
      return merge(s.first, t.second);
    }

    void dump(int x) {
      if(is_null(this)) { return; }
      fprintf(stderr, "%c", "([{"[x%3]);
      lo->dump(x+1);
      fprintf(stderr, "%ld", this->val);
      hi->dump(x+1);
      fprintf(stderr, "%c", ")]}"[x%3]);
    }
  }; // }}}
  Node *root;
  RBST() { root = nullptr; }
  int size() { return root->size(); }
  int indexOf(T val) { return root->indexOf(val); }
  T valueAt(int pos) { return root->valueAt(pos); }
  int lowerBound(T val) { return root->lowerBound(val); }
  int upperBound(T val) { return root->upperBound(val); }
  int count(T val) { return root->count(val); }
  void insert(T val) { root = root->insert(val); }
  void deleteAt(int pos) { root = root->deleteAt(pos); }
  void deleteValue(T val) { deleteAt(indexOf(val)); }
  void dump() { root->dump(0); fprintf(stderr, "\n"); }
};

int main(void) {
  int Q, K; scanf("%d%d", &Q, &K);
  --K;
  RBST<i64> rbst;
  vector<i64> v(Q);
  int cmd; i64 vi;
  int size = 0;
  for(int i=0; i<Q; ++i) {
    scanf("%d", &cmd);
    switch(cmd) {
      case 1:
        scanf("%ld", &vi);
        rbst.insert(vi);
        ++size;
        break;
      case 2:
        if(K < size) {
          printf("%ld\n", rbst.valueAt(K));
          rbst.deleteAt(K);
          --size;
        } else {
          puts("-1");
        }
        break;
    }
  }
  return 0;
}
0