Submission #1305208


Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
struct Node {
    int val;
    Node *lch, *rch;
    int sz;
    Node(int a) :val(a), lch(0), rch(0), sz(1) { init(); }

    void init() { }
    void push() { }
    void update() { }
};

struct dice {
    mt19937 mt; dice() { random_device rd; mt = mt19937(rd()); }
    int operator()(int x) { return this->operator()(0, x - 1); }
    int operator()(int x, int y) { uniform_int_distribution<int> dist(x, y); return dist(mt); }
} dc;
struct RBST {
    RBST() :root(NULL) {}

    Node *root;
    inline int getsz(Node *t) { return t ? t->sz : 0; }
    int getsz() { return getsz(root); }
    inline void push(Node *t) {
        if (t == NULL)return;
        t->push();
    }
    inline Node *update(Node *t) {
        if (!t)return NULL;
        t->sz = getsz(t->lch) + getsz(t->rch) + 1;
        t->update();
        return t;
    }

    Node *merge(Node *a, Node *b) {
        push(a); push(b);
        if (!a)return b;
        if (!b)return a;

        if (dc(getsz(a) + getsz(b))<getsz(a)) {
            a->rch = merge(a->rch, b);
            return update(a);
        }
        else {
            b->lch = merge(a, b->lch);
            return update(b);
        }
    }

    template<class... T> Node *merge(Node *a, T... y) { return merge(a, merge(y...)); }

    pair<Node *, Node *>split(Node *t, int k) {//[0,k) [k,N)
        push(t);
        if (!t)return make_pair(t, t);
        if (k <= getsz(t->lch)) {
            pair<Node *, Node *>s = split(t->lch, k);
            t->lch = s.second;
            return make_pair(s.first, update(t));
        }
        else {
            pair<Node *, Node *>s = split(t->rch, k - getsz(t->lch) - 1);
            t->rch = s.first;
            return make_pair(update(t), s.second);
        }
    }

    int lower_bound(int x) { return lower_bound(root, x); }
    int lower_bound(Node *t, int x) {
        push(t);
        if (!t)return 0;
        if (t->val >= x)return lower_bound(t->lch, x);
        return lower_bound(t->rch, x) + getsz(t->lch) + 1;
    }

    // [l,r]番目でa,b,cに分ける(終わったらちゃんとマージすること)
    // rootは0になってる
    tuple<Node*, Node*, Node*> split3(int l, int r) {
        auto p = split(root, l);

        auto a = p.first;

        auto q = split(p.second, r - l + 1);

        auto b = q.first;
        auto c = q.second;
        root = 0;

        return make_tuple(a, b, c);
    }

    void change(int i, Node* v) { // i番目をvに更新
        auto p = split(root, i);
        auto a = p.first;
        auto q = split(p.second, 1);
        Node* b = q.first;
        auto c = q.second;

        b = v;

        root = merge(merge(a, b), c);
    }

    void dump() {
        dump(root);
        cout << endl;
    }
    void dump(Node *t) {
        if (t == NULL)return;
        push(t);
        dump(t->lch);
        cout << t->val << " ";
        dump(t->rch);
    }
    void push_back(Node *t) {
        root = merge(root, t);
    }

    void insert(int x) {
        int k = lower_bound(x);

        Node *a, *b;
        tie(a, b) = split(root, k);

        root = merge(a, new Node(x), b);
    }

    void erase(int x) {
        int k = lower_bound(x);

        Node *a, *b;
        tie(a, b) = split(root, k);

        Node *ba, *bb;
        tie(ba, bb) = split(b, 1);

        root = merge(a, bb);
    }

    Node* getAt(int i) {
        auto p = split(root, i);
        auto a = p.first;
        auto q = split(p.second, 1);
        Node* b = q.first;
        auto c = q.second;

        root = merge(merge(a, b), c);

        return b;
    }
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/



int Q;
RBST tree;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> Q;
    rep(q, 0, Q) {
        int x, y; cin >> x >> y;
        if (x == 1) {
            tree.insert(y);
        }
        else {
            int ans = tree.getAt(y - 1)->val;
            printf("%d\n", ans);
            tree.erase(ans);
        }
    }
}

Submission Info

Submission Time
Task C - データ構造
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 100
Code Size 4981 Byte
Status AC
Exec Time 441 ms
Memory 9600 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 18
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 11 ms 640 KB
subtask1_05.txt AC 28 ms 1024 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 221 ms 4736 KB
subtask1_08.txt AC 215 ms 5632 KB
subtask1_09.txt AC 195 ms 5632 KB
subtask1_10.txt AC 391 ms 7680 KB
subtask1_11.txt AC 390 ms 7552 KB
subtask1_12.txt AC 368 ms 9600 KB
subtask1_13.txt AC 441 ms 5632 KB
subtask1_14.txt AC 438 ms 5632 KB
subtask1_15.txt AC 144 ms 5632 KB
subtask1_16.txt AC 244 ms 7680 KB