結果

問題 No.618 labo-index
コンテスト
ユーザー mamekin
提出日時 2018-01-14 15:27:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 6,104 bytes
コンパイル時間 1,463 ms
コンパイル使用メモリ 111,992 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-24 02:46:46
合計ジャッジ時間 8,077 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other AC * 1 RE * 34
権限があれば一括ダウンロードができます

ソースコード

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