結果

問題 No.618 labo-index
ユーザー tails
提出日時 2017-12-18 02:16:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 539 ms / 6,000 ms
コード長 1,097 bytes
コンパイル時間 1,464 ms
コンパイル使用メモリ 160,336 KB
実行使用メモリ 52,224 KB
最終ジャッジ日時 2024-12-15 23:38:36
合計ジャッジ時間 9,219 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:49:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   49 | main(){
      | ^~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node {
    int count;
    Node * p1;
    Node * p2;
    Node(){
        count=0;
        p1=0;
        p2=0;
    }
};
void add(Node*p,ll v,ll l,ll r,int inc){
    p->count+=inc;
    if(l<r-1){
        ll c=(l+r)/2;
        if(v<c){
            if(!p->p1){
                p->p1=new Node;
            }
            add(p->p1,v,l,c,inc);
        }else{
            if(!p->p2){
                p->p2=new Node;
            }
            add(p->p2,v,c,r,inc);
        }
    }
}
int count(Node*p,ll v,ll l,ll r){
    ll c=(l+r)/2;
    if(v<c){
        return (p->p1 ? count(p->p1,v,l,c) : 0) + (p->p2 ? p->p2->count : 0);
    }else{
        return (p->p2 ? count(p->p2,v,c,r) : 0);
    }
}
Node * root;
ll a[100010];
int n;
main(){
    root=new Node;
    ll offset=1ll<<49;
    int Q;
    cin>>Q;
    for(int i=0;i<Q;++i){
        int t,x;
        cin>>t>>x;
        if(t==1){
            ll y=x+offset;
            a[++n]=y;
            add(root,y,0,1ll<<50,1);
        }
        if(t==2){
            ll y=a[x];
            add(root,y,0,1ll<<50,-1);
        }
        if(t==3){
            offset-=x;
        }
        {
            int l=0;
            int r=root->count+1;
            while(l<r-1){
                int c=(l+r)/2;
                if(count(root,c+offset-1,0,1ll<<50)>=c){
                    l=c;
                }else{
                    r=c;
                }
            }
            cout<<l<<endl;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0