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

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	mamekin
提出日時	2018-02-10 14:34:57
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	268 ms / 3,000 ms
コード長	5,905 bytes
コンパイル時間	1,217 ms
コンパイル使用メモリ	109,276 KB
実行使用メモリ	9,676 KB
最終ジャッジ日時	2024-04-21 12:29:51
合計ジャッジ時間	6,270 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	267 ms 5,376 KB
testcase_04	AC	181 ms 9,548 KB
testcase_05	AC	175 ms 9,676 KB
testcase_06	AC	183 ms 9,552 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	127 ms 6,604 KB
testcase_13	AC	132 ms 6,612 KB
testcase_14	AC	123 ms 6,484 KB
testcase_15	AC	124 ms 6,364 KB
testcase_16	AC	126 ms 6,596 KB
testcase_17	AC	145 ms 6,484 KB
testcase_18	AC	151 ms 6,480 KB
testcase_19	AC	167 ms 6,484 KB
testcase_20	AC	179 ms 6,480 KB
testcase_21	AC	195 ms 6,608 KB
testcase_22	AC	215 ms 9,552 KB
testcase_23	AC	231 ms 9,552 KB
testcase_24	AC	233 ms 9,552 KB
testcase_25	AC	247 ms 9,556 KB
testcase_26	AC	268 ms 9,556 KB
testcase_27	AC	3 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	91 ms 6,608 KB
testcase_31	AC	92 ms 6,612 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	1 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	1 ms 5,376 KB

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

ソースコード

raw source code

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

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

template <class T>
class Treap
{
private:
    class Node{
    public:
        T val;
        int left, right;
        int num;
        unsigned priority;
        Node(T val){
            this->val = val;
            left      = -1;
            right     = -1;
            num       = 1;
            priority  = xorshift();
        }
    };
    vector<Node> nodes;
    queue<int> q;
    int root;

    // 部分木のノード個数を更新する
    void updateNum(int curr){
        nodes[curr].num = 1;
        if(nodes[curr].left != -1)
            nodes[curr].num += nodes[nodes[curr].left].num;
        if(nodes[curr].right != -1)
            nodes[curr].num += nodes[nodes[curr].right].num;
    }
    // 木の回転処理
    int rotate(int curr, bool isLeftUp){
        int next;
        if(isLeftUp){
            next = nodes[curr].left;
            nodes[curr].left = nodes[next].right;
            nodes[next].right = curr;
        }
        else{
            next = nodes[curr].right;
            nodes[curr].right = nodes[next].left;
            nodes[next].left = curr;
        }
        updateNum(curr);
        updateNum(next);
        return next;
    }
    // 部分木に要素xを追加
    int insert(int curr, const T& x){
        if(curr == -1){
            if(q.empty()){
                nodes.push_back(Node(x));
                return nodes.size() - 1;
            }
            else{
                int i = q.front();
                q.pop();
                nodes[i] = Node(x);
                return i;
            }
        }

        if(x < nodes[curr].val){
            int next = insert(nodes[curr].left, x);
            nodes[curr].left = next;
            updateNum(curr);
            if(nodes[nodes[curr].left].priority < nodes[curr].priority)
                curr = rotate(curr, true);
        }
        else{
            int next = insert(nodes[curr].right, x);
            nodes[curr].right = next;
            updateNum(curr);
            if(nodes[nodes[curr].right].priority < nodes[curr].priority)
                curr = rotate(curr, false);
        }
        return curr;
    }
    // 部分木から要素xを削除（要素xが存在しなければ何もしない）
    int erase(int curr, const T& x){
        if(curr == -1)
            return -1;

        if(nodes[curr].val == x){
            if(nodes[curr].left == -1 && nodes[curr].right == -1){
                q.push(curr);
                return -1;
            }
            if(nodes[curr].right == -1 || (nodes[curr].left != -1 && nodes[nodes[curr].left].priority < nodes[nodes[curr].right].priority)){
                curr = rotate(curr, true);
                nodes[curr].right = erase(nodes[curr].right, x);
            }
            else{
                curr = rotate(curr, false);
                nodes[curr].left = erase(nodes[curr].left, x);
            }
        }
        else{
            if(x < nodes[curr].val)
                nodes[curr].left = erase(nodes[curr].left, x);
            else
                nodes[curr].right = erase(nodes[curr].right, x);
        }
        updateNum(curr);
        return curr;
    }
    // 部分木のi番目の要素を返す
    const T& at(int curr, int i){
        if(nodes[curr].left != -1){
            if(i < nodes[nodes[curr].left].num)
                return at(nodes[curr].left, i);
            i -= nodes[nodes[curr].left].num;
        }
        if(i == 0)
            return nodes[curr].val;
        else
            return at(nodes[curr].right, i-1);
    }
    // 部分木からx未満の値を持つ要素の個数を返す
    int getLowerNum(int curr, const T& x){
        if(curr == -1)
            return 0;

        int ans = 0;
        if(nodes[curr].val < x){
            if(nodes[curr].left != -1)
                ans += nodes[nodes[curr].left].num;
            ans += getLowerNum(nodes[curr].right, x) + 1;
        }
        else{
            ans += getLowerNum(nodes[curr].left, x);
        }
        return ans;
    }

public:
    Treap(){
        root = -1;
    }
    // 要素xを追加
    void insert(const T& x){
        root = insert(root, x);
    }
    // 要素xを削除
    void erase(const T& x){
        root = erase(root, x);
    }
    // 要素の個数を返す
    int size(){
        if(root == -1)
            return 0;
        else
            return nodes[root].num;
    }
    // i番目の要素を返す
    const T& operator[](int i){
        return at(root, i);
    }
    // x未満の値を持つ要素の個数を返す
    int getLowerNum(const T& x){
        return getLowerNum(root, x);
    }
    // 区間[x,y)の値を持つ要素の個数を返す
    int getRangeNum(const T& x, const T& y){
        return getLowerNum(root, y) - getLowerNum(root, x);
    }
};

int main()
{
    int q, k;
    cin >> q >> k;

    Treap<long long> t;
    while(--q >= 0){
        int type;
        cin >> type;

        if(type == 1){
            long long v;
            cin >> v;
            t.insert(v);
        }
        else{
            if(t.size() < k){
                cout << -1 << endl;
            }
            else{
                long long x = t[k-1];
                cout << x << endl;
                t.erase(x);
            }
        }
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード