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

• 問題: No.649 ここでちょっとQK！
• ユーザー: iiljj
• 提出日時: 2020-11-08 16:18:18
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 428 ms / 3,000 ms
• コード長: 19,167 bytes
• コンパイル時間: 2,414 ms
• コンパイル使用メモリ: 211,988 KB
• 実行使用メモリ: 16,000 KB
• 最終ジャッジ日時: 2024-07-22 15:09:47
• 合計ジャッジ時間: 10,679 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	21 ms; 5,376 KB
testcase_04	AC	171 ms; 15,872 KB
testcase_05	AC	168 ms; 16,000 KB
testcase_06	AC	172 ms; 15,872 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	199 ms; 8,448 KB
testcase_13	AC	194 ms; 8,448 KB
testcase_14	AC	188 ms; 8,448 KB
testcase_15	AC	200 ms; 8,576 KB
testcase_16	AC	191 ms; 9,088 KB
testcase_17	AC	221 ms; 9,344 KB
testcase_18	AC	241 ms; 9,728 KB
testcase_19	AC	273 ms; 10,368 KB
testcase_20	AC	299 ms; 10,880 KB
testcase_21	AC	328 ms; 11,264 KB
testcase_22	AC	355 ms; 11,904 KB
testcase_23	AC	348 ms; 12,288 KB
testcase_24	AC	386 ms; 12,800 KB
testcase_25	AC	399 ms; 13,440 KB
testcase_26	AC	428 ms; 13,696 KB
testcase_27	AC	3 ms; 5,376 KB
testcase_28	AC	3 ms; 5,376 KB
testcase_29	AC	3 ms; 5,376 KB
testcase_30	AC	175 ms; 8,448 KB
testcase_31	AC	170 ms; 8,704 KB
testcase_32	AC	2 ms; 5,376 KB
testcase_33	AC	2 ms; 5,376 KB
testcase_34	AC	1 ms; 5,376 KB
testcase_35	AC	1 ms; 5,376 KB

ソースコード

/* #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 log2l

constexpr 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 cerr
void 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 と作用素 E
template <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;
        else
            set_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 */

// Problem
void 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 point
int main() {
    solve();
    return 0;
}