結果

問題 No.649 ここでちょっとQK！
ユーザー PachicobuePachicobue
提出日時 2018-02-23 18:42:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 358 ms / 3,000 ms
コード長 7,063 bytes
コンパイル時間 3,568 ms
コンパイル使用メモリ 210,412 KB
実行使用メモリ 66,304 KB
最終ジャッジ日時 2024-04-17 06:02:54
合計ジャッジ時間 10,819 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 51 ms
66,048 KB
testcase_01 AC 52 ms
66,048 KB
testcase_02 AC 51 ms
66,048 KB
testcase_03 AC 67 ms
66,048 KB
testcase_04 AC 137 ms
65,920 KB
testcase_05 AC 142 ms
66,176 KB
testcase_06 AC 129 ms
66,048 KB
testcase_07 AC 51 ms
66,176 KB
testcase_08 AC 51 ms
66,176 KB
testcase_09 AC 50 ms
66,176 KB
testcase_10 AC 51 ms
66,048 KB
testcase_11 AC 51 ms
65,920 KB
testcase_12 AC 177 ms
66,176 KB
testcase_13 AC 175 ms
66,176 KB
testcase_14 AC 172 ms
66,048 KB
testcase_15 AC 182 ms
66,176 KB
testcase_16 AC 173 ms
66,304 KB
testcase_17 AC 194 ms
66,176 KB
testcase_18 AC 211 ms
66,176 KB
testcase_19 AC 230 ms
65,920 KB
testcase_20 AC 243 ms
66,048 KB
testcase_21 AC 269 ms
66,048 KB
testcase_22 AC 282 ms
65,920 KB
testcase_23 AC 300 ms
65,920 KB
testcase_24 AC 313 ms
66,048 KB
testcase_25 AC 337 ms
66,048 KB
testcase_26 AC 358 ms
66,048 KB
testcase_27 AC 48 ms
66,048 KB
testcase_28 AC 49 ms
66,176 KB
testcase_29 AC 49 ms
65,920 KB
testcase_30 AC 161 ms
66,048 KB
testcase_31 AC 166 ms
66,048 KB
testcase_32 AC 47 ms
66,048 KB
testcase_33 AC 49 ms
66,048 KB
testcase_34 AC 49 ms
66,048 KB
testcase_35 AC 50 ms
66,048 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct OrderedSet {
public:
    static constexpr int POOL_SIZE = 2000000;

private:
    struct Node {
        using T = ll;
        using Ptr = Node*;
        using PtrPair = pair<Ptr, Ptr>;
        Node() : left{}, right{}, value{}, size{1} {}
        Node(const T& value) : left{}, right{}, value{value}, size{1} {}
        Ptr left, right;
        T value;
        int size;

        static void serialize(Ptr a, vector<T>& v)
        {
            if (a == nullptr) {
                return;
            } else {
                serialize(a->left, v);
                v.push_back(a->value);
                serialize(a->right, v);
            }
        }

        static unsigned xor128()
        {
            static unsigned x = 123456789;
            static unsigned y = 362436069;
            static unsigned z = 521288629;
            static unsigned w = 88675123;
            const unsigned t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            return w = (w ^ (w << 19)) ^ (t ^ (t >> 8));
        }

        static unsigned getRand(const int maximum)
        {
            return xor128() % maximum;
        }

        static int getSize(const Ptr a)
        {
            return (a == nullptr) ? 0 : a->size;
        }

        static Ptr update(Ptr a)
        {
            a->size = getSize(a->left) + getSize(a->right) + 1;
            return a;
        }

        static Ptr merge(Ptr a, Ptr b)
        {
            if (a == nullptr) {
                return b;
            } else if (b == nullptr) {
                return a;
            }
            const unsigned asize = getSize(a);
            const unsigned bsize = getSize(b);
            if (getRand(asize + bsize) < asize) {
                a->right = merge(a->right, b);
                return update(a);
            } else {
                b->left = merge(a, b->left);
                return update(b);
            }
        }

        static PtrPair split(Ptr a, const int k)  // size = (k,n-k)
        {
            if (a == nullptr) {
                return make_pair(Ptr{}, Ptr{});
            }
            if (k <= getSize(a->left)) {
                const PtrPair s = split(a->left, k);
                a->left = s.second;
                return make_pair(s.first, update(a));
            } else {
                const PtrPair s = split(a->right, k - getSize(a->left) - 1);
                a->right = s.first;
                return make_pair(update(a), s.second);
            }
        }

        static Ptr insert(Ptr a, const int k, Ptr b)
        {
            const PtrPair s = split(a, k);
            return merge(merge(s.first, b), s.second);
        }

        static PtrPair erase(Ptr a, const int k)
        {
            const PtrPair sr = split(a, k + 1);
            const PtrPair sl = split(sr.first, k);
            return make_pair(merge(sl.first, sr.second), sl.second);
        }
    };

    using Ptr = typename Node::Ptr;
    using PtrPair = typename Node::PtrPair;
    Ptr root;

    int head = 0;
    static Node pool[POOL_SIZE];
    Ptr alloc(const Node::T& x)
    {
        assert(head < POOL_SIZE);
        pool[head].value = x;
        pool[head].size = 1;
        pool[head].left = nullptr;
        pool[head].right = nullptr;
        head++;
        return pool + head - 1;
    }
    void garbage_collect()
    {
        vector<T> v;
        Node::serialize(root, v);
        head = 0;
        root = nullptr;
        for (int i = 0; i < v.size(); i++) {
            root = Node::insert(root, i, alloc(v[i]));
        }
    }

public:
    using T = typename Node::T;
    OrderedSet() : root{} {}

    int size() const
    {
        return Node::getSize(root);
    }

    void insert(const T& value)
    {
        if (head == POOL_SIZE) {
            garbage_collect();
        }
        const int pos = lowerBound(value);
        root = Node::insert(root, pos, alloc(value));
    }

    int lowerBound(const T& x) const
    {
        int res = 0;
        Ptr v = root;
        while (v) {
            if (x < v->value) {
                v = v->left;
            } else if (x == v->value) {
                return res + Node::getSize(v->left);
            } else {
                res += Node::getSize(v->left) + 1;
                v = v->right;
            }
        }
        return res;
    }

    int upperBound(const T& x) const
    {
        int res = 0;
        Ptr v = root;
        while (v) {
            if (x <= v->value) {
                v = v->left;
            } else if (x == v->value) {
                return res + Node::getSize(v->left);
            } else {
                res += Node::getSize(v->left) + 1;
                v = v->right;
            }
        }
        return res;
    }

    void eraseAt(const int k)
    {
        assert(0 <= k);
        assert(k < Node::getSize(root));
        Ptr p;
        tie(root, p) = Node::erase(root, k);
        if (p != nullptr) {
            p->left = Ptr{};
            p->right = Ptr{};
        }
    }

    void erase(const T& value)
    {
        const int pos = lowerBound(value);
        eraseAt(pos);
    }

    bool eraseWithCheck(const T& value)
    {
        const int pos = lowerBound(value);
        if (pos == size()) {
            return false;
        } else if (upperBound(value) == pos) {
            return false;
        } else {
            erase(pos);
            return true;
        }
    }

    T get(int k) const
    {
        assert(0 <= k);
        assert(k < Node::getSize(root));
        Ptr v = root;
        while (v != nullptr) {
            const int s = Node::getSize(v->left);
            if (s > k) {
                v = v->left;
            } else if (s == k) {
                return v->value;
            } else {
                v = v->right;
                k -= s + 1;
            }
        }
        return v->value;
    }

    void set(const int k, const T& value)
    {
        assert(0 <= k);
        assert(k < Node::getSize(root));
        const PtrPair sr = Node::split(root, k + 1);
        const PtrPair sl = Node::split(sr.first, k);
        const Ptr lr = sl.second;
        lr->value = value;
        root = Node::merge(Node::merge(sl.first, lr), sr.second);
    }
};
OrderedSet::Node OrderedSet::pool[OrderedSet::POOL_SIZE];

ostream& operator<<(ostream& os, const OrderedSet& st)
{
    os << "[";
    for (int i = 0; i < st.size(); i++) {
        os << st.get(i) << ",";
    }
    os << "]" << endl;
    return os;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    OrderedSet st;
    int Q, K;
    cin >> Q >> K;
    for (int q = 0; q < Q; q++) {
        int t;
        cin >> t;
        if (t == 1) {
            ll x;
            cin >> x;
            st.insert(x);
        } else {
            if (st.size() >= K) {
                cout << st.get(K - 1) << "\n";
                st.eraseAt(K - 1);
            } else {
                cout << "-1\n";
            }
        }
    }
    return 0;
}
0