結果

問題 No.649 ここでちょっとQK！
ユーザー ZOI-dayoZOI-dayo
提出日時 2024-05-31 23:04:27
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 535 ms / 3,000 ms
コード長 9,881 bytes
コンパイル時間 6,483 ms
コンパイル使用メモリ 400,560 KB
実行使用メモリ 12,800 KB
最終ジャッジ日時 2024-05-31 23:05:22
合計ジャッジ時間 14,658 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 276 ms
6,940 KB
testcase_04 AC 153 ms
12,800 KB
testcase_05 AC 164 ms
12,800 KB
testcase_06 AC 147 ms
12,800 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 214 ms
7,552 KB
testcase_13 AC 202 ms
7,552 KB
testcase_14 AC 201 ms
7,552 KB
testcase_15 AC 219 ms
7,552 KB
testcase_16 AC 213 ms
7,552 KB
testcase_17 AC 245 ms
7,936 KB
testcase_18 AC 262 ms
8,448 KB
testcase_19 AC 290 ms
8,832 KB
testcase_20 AC 335 ms
9,216 KB
testcase_21 AC 355 ms
9,728 KB
testcase_22 AC 385 ms
10,112 KB
testcase_23 AC 429 ms
10,624 KB
testcase_24 AC 451 ms
11,008 KB
testcase_25 AC 483 ms
11,392 KB
testcase_26 AC 535 ms
11,776 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 203 ms
7,552 KB
testcase_31 AC 201 ms
7,424 KB
testcase_32 AC 2 ms
6,944 KB
testcase_33 AC 2 ms
6,940 KB
testcase_34 AC 2 ms
6,944 KB
testcase_35 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "test/yukicoder/649__RBSTMultiSet.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/649"

#line 2 "common/util.hpp"

#line 2 "common/alias.hpp"

#include <boost/multiprecision/cpp_int.hpp>

#include <bits/stdc++.h>
using namespace std;
// using namespace std::views;
// using namespace boost::multiprecision;

// --- 型エイリアス ---
using ll = long long;
using ull = unsigned long long;
template <typename T> using vec = vector<T>;
template <typename T> using vvec = vector<vector<T>>;
template <typename T> using vvvec = vector<vector<vector<T>>>;
template <typename T> using p_queue = priority_queue<T>;
template <typename T> using rp_queue = priority_queue<T, vec<T>, greater<T>>;
using bint = boost::multiprecision::cpp_int;

// --- 黒魔術 ---
#define int ll

// --- 制御マクロ ---
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define all(v) begin(v), end(v)
// #define BIT(n) (1LL << (n))
#define MAX(type) numeric_limits<type>::max()
#define MIN(type) numeric_limits<type>::min()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pb push_back
#define mp make_pair
#define fir first
#define sec second

// --- 定数 ---
constexpr ll INF = 1LL << 60;
// constexpr ll INF = numeric_limits<ll>::max();

inline signed bit_width(ll x) { return bit_width((ull)x); }
inline ull bit_ceil(ll x) { return bit_ceil((ull)x); }
#line 2 "common/concepts.hpp"

#line 4 "common/concepts.hpp"

template <class T>
concept addable = requires(T a, T b) {
  { a + b } -> convertible_to<T>;
};
#line 5 "common/util.hpp"

// --- Utils ---

// 二分探索
template <typename T>
inline T bin_search(T ok, T ng, const function<bool(T)> is_ok) {
  assert(is_ok(ok));
  assert(!is_ok(ng));
  assert(ok < ng);
  while (abs(ok - ng) > 1) {
    T mid = (ok + ng) / 2;
    if (is_ok(mid))
      ok = mid;
    else
      ng = mid;
  }
  return ok;
}

// 順列全探索
inline void rep_perm(int n, function<void(vec<int> &)> f) {
  vec<int> v(n);
  iota(v.begin(), v.end(), 0);
  do {
    f(v);
  } while (next_permutation(v.begin(), v.end()));
}

inline void rep_bit(int n, function<void(int)> f) { rep(i, 1LL << n) f(i); }

// 配列 to string
template <typename T> inline string join(const vec<T> &v, string sep = " ") {
  string res = "";
  rep(i, v.size()) res += to_string(v[i]) + (i == v.size() - 1 ? "" : sep);
  return res;
}
template <typename T>
inline void join_out(ostream &os, const vec<T> &v, string sep = " ",
                     string end = "\n") {
  int n = v.size();
  rep(i, n) os << v[i] << (i == n - 1 ? end : sep);
}

template <typename T>
inline void transform(vec<T> &src, function<void(T &)> f) {
  for (auto &val : src)
    f(val);
}

// ベース指定ceil
inline ll ceil(ll x, ll base) { return (x + base - 1) / base * base; }
// ベース指定floor
inline ll floor(ll x, ll base) { return x / base * base; }

// 合計値を求める
// ll sum(const vec<ll> &v) { return accumulate(all(v), 0LL); }
template <addable T> T sum(const vec<T> &v) { return accumulate(all(v), T()); }

// 可変引数min
template <class... T> auto min(T... a) {
  return min(initializer_list<common_type_t<T...>>{a...});
}

// 可変引数max
template <class... T> auto max(T... a) {
  return max(initializer_list<common_type_t<T...>>{a...});
}

template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

// 3項間不等式
// 広義単調増加
inline bool is_increasing(int x, int y, int z) { return x <= y && y <= z; }

// 半開区間[x, z)にyが含まれるか?
inline bool is_contained(int x, int y, int z) { return x <= y && y < z; }

// 頂点(x, y)が範囲に含まれるか
inline bool is_contained(int H, int W, int x, int y) {
  return is_contained(0, x, H) && is_contained(0, y, W);
}

// rootに対し、aとbが同じ側にあるか (=は含まない)
inline bool is_same_side(int root, int a, int b) {
  return (root < a) == (root < b);
}

// vector継承にする?
template <typename T> struct vec_accumulate : public vec<T> {
  explicit vec_accumulate(vec<T> &v) : vec<T>(v.size()) {
    assert(v.size() > 0);
    this->at(0) = v[0];
    for (int i = 1; i < v.size(); ++i)
      this->at(i) = this->at(i - 1) + v[i];
  }

  // [0, i]の和
  // なので、-1 <= i < size()
  T operator[](int i) {
    assert(is_contained(-1, i, this->size()));
    if (i == -1)
      return T();
    return this->at(i);
  }
};

// vector func
template <typename T> inline void unique_erase(vec<T> &v) {
  sort(all(v));
  v.erase(unique(all(v)), v.end());
}

void io_setup() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);
}
#line 2 "datastructure/rbst_multiset.hpp"

#line 4 "datastructure/rbst_multiset.hpp"

template<typename T>
struct RBST {
private:
  /// 乱数シード生成器
  random_device rd;
  /// 乱数生成器
  mt19937 mt;
  /// 単位元
  T e;
  /// 演算
  function<T(T,T)> F;
protected:
  /// ノード
  struct node_t {
    /// ノードの値
    T val;
    /// 部分木の大きさ
    size_t size;
    /// 部分木の総積
    T sum;
    /// 左右の子
    node_t *lch, *rch;
    /// 値のみによるノードの生成
    node_t(T val): val(val), size(1), sum(val), lch(nullptr), rch(nullptr) {}
    /// 値と子によるノードの生成
    node_t(T val, node_t* lch, node_t* rch): val(val), size(1), sum(val), lch(lch), rch(rch) {}
  };
  /// ノードの値を取得
  inline T val(const node_t* const t) const {
    return t ? t->val : e;
  }
  inline size_t size(const node_t* const t) const {
    return t ? t->size : 0;
  }
  inline T sum(const node_t* const t) const {
    return t ? t->sum : e;
  }
  inline node_t* update(node_t* const t) const {
      t->size = size(t->lch) + size(t->rch) + 1;
      t->sum = F(F(sum(t->lch), val(t)), sum(t->rch));
      return t;
  }
public:
  RBST(T e, function<T(T,T)> F): mt(rd()), e(e), F(F) {}

  node_t* root = nullptr;
  inline node_t* merge(node_t* const l, node_t* const r) {
    if (!l || !r) return l ? l : r;
    if (mt() % (l->size + r->size) < l->size) {
      l->rch = merge(l->rch, r);
      return update(l);
    } else {
      r->lch = merge(l, r->lch);
      return update(r);
    }
  }
  inline pair<node_t*, node_t*> split(node_t* const t, const size_t k) {
    if (!t) return {nullptr, nullptr};
    if (k <= size(t->lch)) {
      auto p = split(t->lch, k);
      t->lch = p.second;
      return {p.first, update(t)};
    } else {
      auto p = split(t->rch, k - size(t->lch) - 1);
      t->rch = p.first;
      return {update(t), p.second};
    }
  }
  inline node_t* insert_at(node_t* t, const size_t k, T val) {
    auto [l, r] = split(t, k);
    return t = merge(merge(l, new node_t(val)), r);
  }
  inline void insert_at(const size_t k, T val) {
    if(!root) root = new node_t(val);
    else root = insert_at(root, k, val);
  }
  inline node_t* erase_at(node_t* t, const size_t k) {
    auto [l, r] = split(t, k);
    auto [ll, lr] = split(r, 1);
    return t = merge(l, lr);
  }
  inline void erase_at(const size_t k) {
    assert(root);
    assert(0 <= k);
    assert(k < root->size);
    if(root->size == 1) {
      delete root;
      root = nullptr;
      return;
    }
    root = erase_at(root, k);
  }
  inline T get_at(const node_t* const t, const size_t k) const {
    assert(t);
    assert(0 <= k);
    assert(k < t->size);
    if(k < size(t->lch)) return get_at(t->lch, k);
    if(k == size(t->lch)) return t->val;
    return get_at(t->rch, k - size(t->lch) - 1);
  }

  inline T get_at(const size_t k) const {
    return get_at(root, k);
  }
  inline T query(node_t* &t, const size_t l, const size_t r) {
    auto [left, mid_right] = split(t, l);
    auto [mid, right] = split(mid_right, r - l);
    T res = sum(mid);
    t = merge(merge(left, mid), right);
    return res;
  }
  inline T query(const size_t l, const size_t r) {
    return query(root, l, r);
  }
  inline size_t size() const {
    return size(root);
  }

};

template<typename T>
struct RBSTMultiSet : public RBST<T> {
private:
  using node_t = typename RBST<T>::node_t;
public:
  RBSTMultiSet(): RBST<T>(0, [](T a, T b){return a;}) {}

  size_t lower_bound(node_t* t, T val) {
    if(!t) return 0;
    if(val <= this->val(t)) return lower_bound(t->lch, val);
    return this->size(t->lch) + 1 + lower_bound(t->rch, val);
  }
  size_t lower_bound(T val) {
    return lower_bound(this->root, val);
  }
  size_t upper_bound(node_t* t, T val) {
    if(!t) return 0;
    if(val < t->val) return upper_bound(t->lch, val);
    return this->size(t->lch) + 1 + upper_bound(t->rch, val);
  }
  size_t upper_bound(T val) {
    return upper_bound(this->root, val);
  }
  void insert(T val) {
    this->insert_at(lower_bound(val), val);
  }
  size_t count(T val) {
    return upper_bound(val) - lower_bound(val);
  }
  bool contains(T val) {
    int idx = lower_bound(val);
    return idx < this->root->size && this->get_at(idx)->val == val;
  }
  void erase(T val) {
    int idx = lower_bound(val);
    if(idx < this->root->size && this->get_at(idx)->val == val) {
      this->erase_at(idx);
    }
  }
};

template<typename T>
struct RBSTSet : public RBSTMultiSet<T> {
public:
  RBSTSet(): RBSTMultiSet<T>() {}
  void insert(T val) {
    if(contains(val)) return;
    this->insert(val, lower_bound(val));
  }
};
#line 5 "test/yukicoder/649__RBSTMultiSet.test.cpp"

signed main() {
  io_setup();
  int Q, K;
  cin >> Q >> K;
  K--;
  RBSTMultiSet<int> tree;
  rep(q, Q) {
    int type;
    cin >> type;
    if (type == 1) {
      int v;
      cin >> v;
      tree.insert(v);
    } else {
      if(K >= tree.size()) {
        cout << -1 << endl;
        continue;
      }
      cout << tree.get_at(K) << endl;
      tree.erase_at(K);
    }
  }
}
0