結果

問題 No.618 labo-index
ユーザー mamekinmamekin
提出日時 2018-01-14 15:27:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 6,104 bytes
コンパイル時間 1,015 ms
コンパイル使用メモリ 114,024 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-06 11:35:52
合計ジャッジ時間 7,486 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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){
            nodes[curr].left = insert(nodes[curr].left, x);
            updateNum(curr);
            if(nodes[nodes[curr].left].priority < nodes[curr].priority)
                curr = rotate(curr, true);
        }
        else{
            nodes[curr].right = insert(nodes[curr].right, x);
            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;
    cin >> q;

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

        if(type == 1){
            v.push_back(x - offset);
            t.insert(x - offset);
        }
        else if(type == 2){
            t.erase(v[x-1]);
        }
        else{
            offset += x;
        }

        int n = t.size();
        int left = 0;
        int right = n;
        while(left < right){
            int mid = (left + right) / 2;
            if(n - mid <= t[mid] + offset)
                right = mid;
            else
                left = mid + 1;
        }
        cout << (n - left) << endl;
    }

    return 0;
}
0