結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 2020-11-08 16:18:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 496 ms / 3,000 ms |
コード長 | 19,167 bytes |
コンパイル時間 | 2,018 ms |
コンパイル使用メモリ | 206,012 KB |
最終ジャッジ日時 | 2025-01-15 21:39:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
/* #region Head */// #define _GLIBCXX_DEBUG#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using ld = long double;using pll = pair<ll, ll>;template <class T> using vc = vector<T>;template <class T> using vvc = vc<vc<T>>;using vll = vc<ll>;using vvll = vvc<ll>;using vld = vc<ld>;using vvld = vvc<ld>;using vs = vc<string>;using vvs = vvc<string>;template <class T, class U> using um = unordered_map<T, U>;template <class T> using pq = priority_queue<T>;template <class T> using pqa = priority_queue<T, vc<T>, greater<T>>;template <class T> using us = unordered_set<T>;#define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i))#define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i))#define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i))#define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d))#define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d))#define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)#define ALL(x) begin(x), end(x)#define SIZE(x) ((ll)(x).size())#define PERM(c) \sort(ALL(c)); \for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))#define UNIQ(v) v.erase(unique(ALL(v)), v.end());#define CEIL(a, b) (((a) + (b)-1) / (b))#define endl '\n'#define sqrt sqrtl#define floor floorl#define log2 log2lconstexpr ll INF = 1'010'000'000'000'000'017LL;constexpr int IINF = 1'000'000'007LL;constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7// constexpr ll MOD = 998244353;constexpr ld EPS = 1e-12;constexpr ld PI = 3.14159265358979323846;template <typename T> istream &operator>>(istream &is, vc<T> &vec) { // vector 入力for (T &x : vec) is >> x;return is;}template <typename T> ostream &operator<<(ostream &os, vc<T> &vec) { // vector 出力 (for dump)os << "{";REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", ");os << "}";return os;}template <typename T> ostream &operator>>(ostream &os, vc<T> &vec) { // vector 出力 (inline)REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " ");return os;}template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var) { // pair 入力is >> pair_var.first >> pair_var.second;return is;}template <typename T, typename U> ostream &operator<<(ostream &os, pair<T, U> &pair_var) { // pair 出力os << "(" << pair_var.first << ", " << pair_var.second << ")";return os;}// map, um, set, us 出力template <class T> ostream &out_iter(ostream &os, T &map_var) {os << "{";REPI(itr, map_var) {os << *itr;auto itrcp = itr;if (++itrcp != map_var.end()) os << ", ";}return os << "}";}template <typename T, typename U> ostream &operator<<(ostream &os, map<T, U> &map_var) { return out_iter(os, map_var); }template <typename T, typename U> ostream &operator<<(ostream &os, um<T, U> &map_var) {os << "{";REPI(itr, map_var) {auto [key, value] = *itr;os << "(" << key << ", " << value << ")";auto itrcp = itr;if (++itrcp != map_var.end()) os << ", ";}os << "}";return os;}template <typename T> ostream &operator<<(ostream &os, set<T> &set_var) { return out_iter(os, set_var); }template <typename T> ostream &operator<<(ostream &os, us<T> &set_var) { return out_iter(os, set_var); }template <typename T> ostream &operator<<(ostream &os, pq<T> &pq_var) {pq<T> pq_cp(pq_var);os << "{";if (!pq_cp.empty()) {os << pq_cp.top(), pq_cp.pop();while (!pq_cp.empty()) os << ", " << pq_cp.top(), pq_cp.pop();}return os << "}";}void pprint() { cout << endl; }template <class Head, class... Tail> void pprint(Head &&head, Tail &&... tail) {cout << head;if (sizeof...(Tail) > 0) cout << ' ';pprint(move(tail)...);}// dump#define DUMPOUT cerrvoid dump_func() { DUMPOUT << endl; }template <class Head, class... Tail> void dump_func(Head &&head, Tail &&... tail) {DUMPOUT << head;if (sizeof...(Tail) > 0) DUMPOUT << ", ";dump_func(move(tail)...);}// chmax (更新「される」かもしれない値が前)template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) {if (comp(xmax, x)) {xmax = x;return true;}return false;}// chmin (更新「される」かもしれない値が前)template <typename T, typename U, typename Comp = less<>> bool chmin(T &xmin, const U &x, Comp comp = {}) {if (comp(x, xmin)) {xmin = x;return true;}return false;}// ローカル用#define DEBUG_#ifdef DEBUG_#define DEB#define dump(...) \DUMPOUT << " " << string(#__VA_ARGS__) << ": " \<< "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \<< " ", \dump_func(__VA_ARGS__)#else#define DEB if (false)#define dump(...)#endif#define VAR(type, ...) \type __VA_ARGS__; \cin >> __VA_ARGS__;template <typename T> istream &operator,(istream &is, T &rhs) { return is >> rhs; }template <typename T> ostream &operator,(ostream &os, const T &rhs) { return os << ' ' << rhs; }struct AtCoderInitialize {static constexpr int IOS_PREC = 15;static constexpr bool AUTOFLUSH = false;AtCoderInitialize() {ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cout << fixed << setprecision(IOS_PREC);if (AUTOFLUSH) cout << unitbuf;}} ATCODER_INITIALIZE;void Yn(bool p) { cout << (p ? "Yes" : "No") << endl; }void YN(bool p) { cout << (p ? "YES" : "NO") << endl; }/* #endregion */// #include <atcoder/all>// using namespace atcoder;/* #region RBST */// https://ei1333.github.io/luzhiled/snippets/structure/rbst.html// モノイド T と作用素 Etemplate <class T, class E = T> struct RandomizedBinarySearchTree {using F = function<T(T, T)>;using G = function<T(T, E)>;using H = function<E(E, E)>;using P = function<E(E, size_t)>;// 乱数生成 (xorshift)inline static uint32_t xor128() {static uint32_t x = 123456789;static uint32_t y = 362436069;static uint32_t z = 521288629;static uint32_t w = 88675123;uint32_t t;t = x ^ (x << 11);x = y;y = z;z = w;return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));}// 木のノードstruct Node {Node *l = nullptr, *r = nullptr;size_t cnt = 1ul;T key, sum;E lazy;Node() = default;// 値 k を持つノードをつくる.作用素は p で初期化する.Node(const T &k, const E &p) : key(k), sum(k), lazy(p) {}};using NodePair = pair<Node *, Node *>;Node *root = nullptr; // 根const T ti; // 要素の単位元,1 など.const E ei; // 作用素の単位元,0 など.const F f; // 要素と要素をマージする関数const G g; // 要素に作用素を作用させる関数const H h; // 作用素と作用素をマージする関数const P p; // 要素に作用素を作用させる前に,区間の長さを考慮して作用素を加工して返す関数.// (作用素, 区間長さ) ->加工済み作用素./*** コンストラクタ.遅延伝播・区間クエリを行わない場合はこちら.* @param sz ノード数* @param f 要素と要素をマージする関数* @param ti 要素の単位元*/RandomizedBinarySearchTree(const F &f, const T &ti) : ti(ti), ei(E()), f(f), g(G()), h(H()), p(P()) {}/*** コンストラクタ.* @param f 要素と要素をマージする関数* @param g 要素に作用素を作用させる関数* @param h 作用素と作用素をマージする関数* @param p 要素に作用素を作用させる前に,区間の長さを考慮して作用素を加工して返す関数.* (作用素, 区間長さ) -> 加工済み作用素.* @param ti 要素の単位元* @param ei 作用素の単位元*/RandomizedBinarySearchTree(const F &f, const G &g, const H &h, const P &p, const T &ti, const E &ei): ti(ti), ei(ei), f(f), g(g), h(h), p(p) {}// デストラクタ~RandomizedBinarySearchTree() { sweep(root); }private:// 新しいノードを生成するinline Node *alloc(const T &key) { return new Node(key, ei); }virtual Node *clone(Node *t) { return t; }inline T sum(const Node *t) const { return t ? t->sum : ti; }// 子ノード再計算済み状態で,指定ノードの値を再計算するinline Node *recalc(Node *t) {t->cnt = count(t->l) + count(t->r) + 1ul;t->sum = f(f(sum(t->l), t->key), sum(t->r));return t;}// 遅延を子ノードへ伝播するNode *propagate(Node *t) {t = clone(t);if (t->lazy != ei) {t->key = g(t->key, p(t->lazy, 1));if (t->l) {t->l = clone(t->l);t->l->lazy = h(t->l->lazy, t->lazy);t->l->sum = g(t->l->sum, p(t->lazy, count(t->l)));}if (t->r) {t->r = clone(t->r);t->r->lazy = h(t->r->lazy, t->lazy);t->r->sum = g(t->r->sum, p(t->lazy, count(t->r)));}t->lazy = ei;}return recalc(t);}// 木 l と木 r を併合するNode *merge(Node *l, Node *r) {if (!l || !r) return l ? l : r;if (xor128() % (l->cnt + r->cnt) < l->cnt) {l = propagate(l);l->r = merge(l->r, r);return recalc(l);} else {r = propagate(r);r->l = merge(l, r->l);return recalc(r);}}// 木 t を [0,k) [k,n) で分割するNodePair split(Node *t, size_t k) {if (!t) return {t, t};t = propagate(t);if (k <= count(t->l)) {NodePair s = split(t->l, k);t->l = s.second;return {s.first, recalc(t)};} else {NodePair s = split(t->r, k - count(t->l) - 1);t->r = s.first;return {recalc(t), s.second};}}Node *build(size_t l, size_t r, const vc<T> &v) {if (l + 1 >= r) return alloc(v[l]);return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v));}// 木 t を再帰的に辿って,通りがけ順に値を配列に詰めていくvoid _dump(Node *t, typename vc<T>::iterator &it) {if (!t) return;t = propagate(t);_dump(t->l, it);*it = t->key;_dump(t->r, ++it);}// 木 t の各ノードを通りがけ順に格納したものを返す.O(n).vc<T> _dump(Node *t) {vc<T> v(count(t));typename vc<T>::iterator it = begin(v);_dump(t, it);return v;}// 木 t の位置 k にノード v を挿入するvoid insert(Node *&t, size_t k, const T &v) {NodePair x = split(t, k);t = merge(merge(x.first, alloc(v)), x.second);}// 木 t の位置 k のノードを削除するvoid erase(Node *&t, size_t k) {NodePair x = split(t, k);NodePair y = split(x.second, 1);delete y.first;t = merge(x.first, y.second);}// 木を再帰的に消していくvoid sweep(Node *r) const {if (r == nullptr) return;if (r->l != nullptr) {sweep(r->l);r->l = nullptr;}if (r->r != nullptr) {sweep(r->r);r->r = nullptr;}delete r;}// 木 t の区間 [a, b) の値を二項演算した結果を返すT query(Node *&t, size_t a, size_t b) {assert(b > a);NodePair x = split(t, a); // 区間始点で左右に分割NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割T ret = sum(y.first);t = merge(x.first, merge(y.first, y.second));return ret;}// 木 t の区間 [a, b) に作用素 p を適用するvoid update(Node *&t, size_t a, size_t b, const E &p) {assert(b > a);NodePair x = split(t, a); // 区間始点で左右に分割NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割y.first->lazy = h(y.first->lazy, p);t = merge(x.first, merge(propagate(y.first), y.second));}// 木 t の k (0-indexed) 番目の値を x に変更するvoid set_val(Node *&t, size_t k, const T &x) {t = propagate(t);if (k < count(t->l))set_val(t->l, k, x);else if (k == count(t->l))t->key = t->sum = x;elseset_val(t->r, k - count(t->l) - 1, x);t = recalc(t);}// 木 t が空木かどうかを返すstatic bool empty(Node *t) { return !t; }protected:// 木 t のノード数を返すinline static size_t count(const Node *t) { return t ? t->cnt : 0ul; }public:// 木 root のノード数を返すsize_t size() const { return count(root); }// ベクトル v をもとに木を構築する.O(n).Node *build(const vc<T> &v) {// ptr = 0;return build(0ul, v.size(), v);}// 木 root の位置 k にノード v を挿入するvoid insert(size_t k, const T &v) {NodePair x = split(root, k);root = merge(merge(x.first, alloc(v)), x.second);}// 木 root の位置 k のノードを削除するvoid erase(size_t k) {NodePair x = split(root, k);NodePair y = split(x.second, 1);delete y.first;root = merge(x.first, y.second);}// 木 root の区間 [a, b) の値を二項演算した結果を返すT query(size_t a, size_t b) { return query(root, a, b); }// 木 root の区間 [a, b) に作用素 p を適用するvoid update(size_t a, size_t b, const E &p) { update(a, b, p); }// 木 root の k (0-indexed) 番目の値を x に変更するvoid set_val(size_t k, const T &x) { set_val(root, k, x); }// 木 root が空木かどうかを返すbool empty() { return empty(root); }// 木 root の各ノードを通りがけ順に格納したものを返す.O(n).vc<T> _dump() { return _dump(root); }};/* #endregion *//* #region OrderedSet */// k 番目が取れる多重集合(昇順ソート済みベクトルとして扱える)template <class T> struct OrderedMultiSet : RandomizedBinarySearchTree<T> {using RBST = RandomizedBinarySearchTree<T>;using Node = typename RBST::Node;// コンストラクタOrderedMultiSet() : RBST([](T x, [[maybe_unused]] T y) -> T { return x; }, T()) {}// 多重集合のサイズを返すsize_t size() const { return RBST::size(); }// 多重集合に値 x を挿入するvirtual void insert(const T &x) { RBST::insert(lower_bound(x), x); }// 多重集合から値 x を削除するvoid erase(const T &x) {if (!count(x)) return;RBST::erase(lower_bound(this->root, x));}void erase_kth_element(const size_t k) {assert(k < size());RBST::erase(k);}// 多重集合 の k (0-indexed) 番目の要素を返すT kth_element(size_t k) const { return kth_element(this->root, k); }// 多重集合に含まれる値 x の個数を返すsize_t count(const T &x) const { return count(this->root, x); }// x 以上の最小の要素のインデックスを返すsize_t lower_bound(const T &x) const { return lower_bound(this->root, x); }// x より大きい最小の要素のインデックスを返すsize_t upper_bound(const T &x) const { return upper_bound(this->root, x); }private:// k (0-indexed) 番目の要素を返すT kth_element(Node *t, size_t k) const {assert(k < RBST::count(t));if (k < RBST::count(t->l)) return kth_element(t->l, k);if (k == RBST::count(t->l)) return t->key;return kth_element(t->r, k - RBST::count(t->l) - 1);}// 木 t に含まれる値 x の個数を返すsize_t count(Node *t, const T &x) const { return upper_bound(t, x) - lower_bound(t, x); }// 木 t に含まれる x 以上の最小の要素のインデックスを返すsize_t lower_bound(Node *t, const T &x) const {if (!t) return 0ul;if (x <= t->key) return lower_bound(t->l, x);return lower_bound(t->r, x) + RBST::count(t->l) + 1ul;}// 木 t に含まれる x より大きい最小の要素のインデックスを返すsize_t upper_bound(Node *t, const T &x) const {if (!t) return 0ul;if (x < t->key) return upper_bound(t->l, x);return upper_bound(t->r, x) + RBST::count(t->l) + 1ul;}};// 1 種類の値は1つのみ格納する通常の集合,k 番目が取れるようになったものtemplate <class T> struct OrderedSet : OrderedMultiSet<T> {using SET = OrderedMultiSet<T>;using RBST = typename SET::RBST;using Node = typename RBST::Node;OrderedSet() : OrderedMultiSet<T>() {}// 集合に値 x を挿入する.既に値 x が存在する場合は何もしない.void insert(const T &x) override {if (SET::count(x)) return;RBST::insert(SET::lower_bound(x), x);}};/* #endregion */// Problemvoid solve() {VAR(size_t, q, k);--k;OrderedMultiSet<ll> st;REP(i, 0, q) {VAR(int, t);if (t == 1) {VAR(ll, v);// v を追加する// dump(i, v);st.insert(v);} else {// k 番目に小さい要素を出力if (k >= st.size()) {pprint(-1);continue;}ll ret = st.kth_element(k);st.erase(ret);pprint(ret);}// dump(st._dump());}}// entry pointint main() {solve();return 0;}