#708110 (C++17) No.649 ここでちょっとQK！

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	Suu0313
提出日時	2021-10-18 20:19:34
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	300 ms / 3,000 ms
コード長	10,056 bytes
コンパイル時間	2,166 ms
コンパイル使用メモリ	205,624 KB
実行使用メモリ	19,072 KB
最終ジャッジ日時	2024-09-19 16:37:18
合計ジャッジ時間	8,163 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	280 ms 6,940 KB
testcase_04	AC	225 ms 19,072 KB
testcase_05	AC	227 ms 19,072 KB
testcase_06	AC	233 ms 19,072 KB
testcase_07	AC	1 ms 6,944 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	136 ms 9,728 KB
testcase_13	AC	134 ms 9,728 KB
testcase_14	AC	132 ms 9,728 KB
testcase_15	AC	134 ms 9,856 KB
testcase_16	AC	132 ms 10,240 KB
testcase_17	AC	157 ms 10,880 KB
testcase_18	AC	168 ms 11,520 KB
testcase_19	AC	185 ms 12,160 KB
testcase_20	AC	203 ms 12,672 KB
testcase_21	AC	223 ms 13,184 KB
testcase_22	AC	234 ms 13,952 KB
testcase_23	AC	246 ms 14,592 KB
testcase_24	AC	280 ms 15,104 KB
testcase_25	AC	286 ms 15,744 KB
testcase_26	AC	300 ms 16,384 KB
testcase_27	AC	3 ms 6,940 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	3 ms 6,940 KB
testcase_30	AC	95 ms 9,600 KB
testcase_31	AC	95 ms 10,240 KB
testcase_32	AC	1 ms 6,944 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	2 ms 6,940 KB
testcase_35	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

template<typename T, class Compair = less<T>>
struct RedBlackTree{
private:
  enum Color{RED, BLACK, NIL};

  struct Node{
    T key;
    Color color;
    size_t sz = 0;
    Node *parentP = nullptr, *leftP = nullptr, *rightP = nullptr, *nextP = nullptr, *prevP = nullptr;

    constexpr Node(): key{}, color(NIL) {}
    constexpr Node(const T &key, Color color): key(key), color(color), sz(1) {}

    constexpr bool is_valid() const { return color != NIL; }
    constexpr bool is_nil() const { return color == NIL; }
    constexpr bool is_red() const { return color == RED; }
    constexpr bool is_black() const { return color != RED; }

    constexpr bool is_left() const { return parentP->leftP == this; }
    constexpr bool is_right() const { return parentP->rightP == this; }
    constexpr bool is_root() const { return parentP->is_nil(); }

    constexpr void flip_color(){
      assert(is_valid());
      if(is_red()) color = BLACK;
      else color = RED;
    }
  };
  using Np = Node*;

  static Np get_nil(){
    static Node nil = Node{};
    return &nil;
  }

  Np root = get_nil();
  const Compair cmp;

  void rotate_left(Np t){
    Np y = t->rightP;
    assert(y->is_valid());

    t->rightP = y->leftP;
    if(y->leftP->is_valid()) y->leftP->parentP = t;
    y->parentP = t->parentP;

    if(t->is_root()) root = y;
    else if(t->is_left()) t->parentP->leftP = y;
    else t->parentP->rightP = y;

    y->leftP = t;
    t->parentP = y;

    y->sz = t->sz;
    t->sz = t->leftP->sz + t->rightP->sz + 1;
  }

  void rotate_right(Np t){
    Np y = t->leftP;
    assert(y->is_valid());

    t->leftP = y->rightP;
    if(y->rightP->is_valid()) y->rightP->parentP = t;
    y->parentP = t->parentP;

    if(t->is_root()) root = y;
    else if(t->is_left()) t->parentP->leftP = y;
    else t->parentP->rightP = y;

    y->rightP = t;
    t->parentP = y;

    y->sz = t->sz;
    t->sz = t->leftP->sz + t->rightP->sz + 1;
  }

  void insert_fixup(Np t){
    assert(!!t->parentP);
    while(t->parentP->is_red()){
      if(t->parentP->is_left()){
        Np y = t->parentP->parentP->rightP;
        if(y->is_red()){
          t->parentP->flip_color();
          y->flip_color();
          t->parentP->parentP->flip_color();
          t = t->parentP->parentP;
        }else{
          if(t->is_right()){
            t = t->parentP;
            rotate_left(t);
          }
          t->parentP->flip_color();
          t->parentP->parentP->flip_color();
          rotate_right(t->parentP->parentP);
        }
      }else{
        Np y = t->parentP->parentP->leftP;
        if(y->is_red()){
          t->parentP->flip_color();
          y->flip_color();
          t->parentP->parentP->flip_color();
          t = t->parentP->parentP;
        }else{
          if(t->is_left()){
            t = t->parentP;
            rotate_right(t);
          }
          t->parentP->flip_color();
          t->parentP->parentP->flip_color();
          rotate_left(t->parentP->parentP);
        }
      }
    }
    if(root->is_red()) root->flip_color();
  }

  void erase_impl(Np t){
    Np x = get_nil(), y = t;
    Color color = y->color;
    if(t->leftP->is_nil()){
      x = t->rightP;
      transplant(t, t->rightP);
    }else if(t->rightP->is_nil()){
      x = t->leftP;
      transplant(t, t->leftP);
    }else{
      y = y->nextP;
      assert(y->is_valid());
      Np m = y->parentP;
      while(m != t){
        m->sz -= 1;
        m = m->parentP;
      }
      color = y->color;
      x = y->rightP;
      if(y->parentP == t) x->parentP = y;
      else{
        transplant(y, y->rightP);
        y->rightP = t->rightP;
        y->rightP->parentP = y;
      }
      transplant(t, y);
      y->leftP = t->leftP;
      y->leftP->parentP = y;
      y->color = t->color;
      y->sz = t->sz;
    }

    if(color == BLACK) erase_fixup(x);
    t->nextP->prevP = t->prevP;
    t->prevP->nextP = t->nextP;
    delete t;
  }

  void erase_fixup(Np t){
    while(!t->is_root() && t->is_black()){
      if(t->is_left()){
        Np y = t->parentP->rightP;
        if(y->is_red()){
          y->flip_color(); t->parentP->flip_color();
          rotate_left(t->parentP);
          y = t->parentP->rightP;
        }
        if(y->leftP->is_black() && y->rightP->is_black()){
          y->flip_color(); t = t->parentP;
        }else{
          if(y->rightP->is_black()){
            y->leftP->flip_color();
            y->flip_color();
            rotate_right(y);
            y = t->parentP->rightP;
          }
          y->color = t->parentP->color;
          t->parentP->color = BLACK;
          y->rightP->color = BLACK;
          rotate_left(t->parentP);
          t = root;
        }
      }else{
        Np y = t->parentP->leftP;
        if(y->is_red()){
          y->flip_color(); t->parentP->flip_color();
          rotate_right(t->parentP);
          y = t->parentP->leftP;
        }
        if(y->leftP->is_black() && y->rightP->is_black()){
          y->flip_color(); t = t->parentP;
        }else{
          if(y->leftP->is_black()){
            y->rightP->flip_color();
            y->flip_color();
            rotate_left(y);
            y = t->parentP->leftP;
          }
          y->color = t->parentP->color;
          t->parentP->color = BLACK;
          y->leftP->color = BLACK;
          rotate_right(t->parentP);
          t = root;
        }
      }
    }
    if(t->is_red()) t->flip_color();
  }

  void transplant(Np u, Np v){
    if(u->is_root()) root = v;
    else if(u->is_left()) u->parentP->leftP = v;
    else u->parentP->rightP = v;
    v->parentP = u->parentP;
  }

  Np minimum(Np t) const {
    while(t->leftP->is_valid()) t = t->leftP;
    return t;
  }

  Np maximum(Np t) const {
    while(t->rightP->is_valid()) t = t->rightP;
    return t;
  }

  Np minimum() const { return get_nil()->nextP; }
  Np maximum() const { return get_nil()->prevP; }

  Np successor(Np t) const { return t->nextP; }

  Np predecessor(Np t) const { return t->prevP; }

  Np lower_bound(Np t, const T &key) const {
    if(t->is_nil()) return t;
    if(cmp(t->key, key)) return lower_bound(t->rightP, key);
    Np l = lower_bound(t->leftP, key);
    if(l->is_nil()) return t;
    return l;
  }

  Np upper_bound(Np t, const T &key) const {
    if(t->is_nil()) return t;
    if(!cmp(key, t->key)) return upper_bound(t->rightP, key);
    Np l = upper_bound(t->leftP, key);
    if(l->is_nil()) return t;
    return l;
  }

  Np select(Np t, size_t k) const {
    assert(!!t);
    size_t r = t->leftP->sz;
    if(k == r) return t;
    else if(k < r) return select(t->leftP, k);
    else return select(t->rightP, k - r - 1);
  }

  void dump(Np t) const {
    if(t->is_nil()) return;
    dump(t->leftP);
    cout << t->key << " ";
    dump(t->rightP);
  }

  size_t rank(Np t) const {
    if(t->is_nil()) return size();
    size_t r = t->leftP->sz;
    Np y = t;
    while(!y->is_root()){
      if(y->is_right()) r += y->parentP->leftP->sz + 1;
      y = y->parentP;
    }
    return r;
  }

  Np find(const T &key) const {
    Np t = root;
    while(t->is_valid() && t->key != key){
      if(cmp(key, t->key)) t = t->leftP;
      else t = t->rightP;
    }
    return t;
  }

public:

  RedBlackTree(const Compair &cmp = Compair{}): cmp(cmp) {
    root->nextP = root->prevP = get_nil();
  }
  RedBlackTree(initializer_list<T> v ,const Compair &cmp = Compair{}): cmp(cmp) {
    root->nextP = root->prevP = get_nil();
    for(auto&e : v) insert(e);
  }

  size_t insert(const T &key){
    Np t = new Node(key, RED);
    t->leftP = t->rightP = t->nextP = t->prevP = get_nil();

    Np x = root, y = get_nil();
    while(x->is_valid()){
      y = x;
      if(cmp(key, x->key)) x = x->leftP;
      else x = x->rightP;
      y->sz += 1;
    }
    assert(!!y);
    t->parentP = y;
    if(y->is_nil()){
      root->nextP = root->prevP = t;  root = t;
    }else if(cmp(key, y->key)){
      y->leftP = t; y->prevP->nextP = t; t->nextP = y; t->prevP = y->prevP; y->prevP = t; 
    }else{
      y->rightP = t; y->nextP->prevP = t; t->prevP = y; t->nextP = y->nextP; y->nextP = t;
    }

    insert_fixup(t);
    return rank(t);
  }

  bool erase(const T &key){
    Np t = find(key);
    if(t->is_nil()) return false;
    assert(t->key == key);
    Np y = t;
    while(y->is_valid()){
      y->sz -= 1;
      y = y->parentP;
    }
    erase_impl(t);
    return true;
  }

  bool exist(const T &key) const { return find(key)->is_valid(); }

  void dump() const {
    dump(root);
    cout << endl;
  }

  size_t lower_bound(const T &key) const { return rank(lower_bound(root, key)); }
  size_t upper_bound(const T &key) const { return rank(upper_bound(root, key)); }

  T at(int k) const {
    if(k < 0) k += (int)size();
    assert(0 <= k && k < (int)size());
    return select(root, k)->key;
  }

  T operator[](int k) const {
    if(k < 0) k += (int)size();
    assert(0 <= k && k < (int)size());
    return select(root, k)->key;
  }

  T pop(int k){ T key = at(k); erase(key); return key; }

  size_t size() const { return root->sz; }

  struct itr{
    Np t;
    RedBlackTree<T> &tree;
    bool operator!=(const itr &it) const { return t != it.t; }
    void operator++(){ t = tree.successor(t); }
    void operator--(){ tree.predecessor(t); }
    T operator*() const { return t->key; }
  };

  struct ritr{
    Np t;
    RedBlackTree<T> &tree;
    bool operator!=(const ritr &it) const { return t != it.t; }
    void operator++(){ t = tree.predecessor(t); }
    void operator--(){ t = tree.successor(t);
    }
    T operator*() const { return t->key; }
  };

  itr begin(){ return {minimum(), *this}; }
  itr end(){ return {get_nil(), *this}; }
  ritr rbegin(){ return {maximum(), *this}; }
  ritr rend(){ return {get_nil(), *this}; }
};


int main() {
  RedBlackTree<int64_t> rbt;
  int q; size_t k;
  cin >> q >> k;
  --k;
  while(q--){
    int t; cin >> t;
    if(t == 1){
      int64_t v; cin >> v;
      rbt.insert(v);
    }else{
      if(rbt.size() <= k) cout << "-1\n";
      else cout << rbt.pop(k) << "\n";
    }
  }
}

yukicoder

結果

テストケース

ソースコード