結果

問題 No.618 labo-index
コンテスト
ユーザー rickytheta
提出日時 2017-12-18 00:17:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 190 ms / 6,000 ms
コード長 4,303 bytes
コンパイル時間 1,731 ms
コンパイル使用メモリ 167,552 KB
実行使用メモリ 8,916 KB
最終ジャッジ日時 2024-12-15 23:20:10
合計ジャッジ時間 4,957 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:150:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  150 |   scanf("%d",&q);
      |   ~~~~~^~~~~~~~~
main.cpp:155:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  155 |     scanf("%d%d",&t,&x);
      |     ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

struct Treap{
private:
  static const ll rd_msk = (1ll<<32)-1;
  static ll rd(){
    static ll rd_x = 123456789;
    static ll rd_y = 362436069;
    static ll rd_z = 521288629;
    static ll rd_w = 88675123;
    ll t = (rd_x^(rd_x<<11))&rd_msk;
    rd_x = rd_y;
    rd_y = rd_z;
    rd_z = rd_w;
    return rd_w = (rd_w^(rd_w>>19)) ^ (t^(t>>8));
  }
  struct node{
    ll val,pri,cnt;;
    node *lch, *rch;
    node(ll val):val(val),cnt(1){
      pri = rd();
      lch = rch = NULL;
    }
  };
public:
  node *root;
  Treap():root(NULL){}
private:
  ll count(node *t){return t==NULL?0:t->cnt;}
  node* update(node *t){t->cnt=count(t->lch)+count(t->rch)+1;return t;}
  node* merge(node *l, node *r){
    if(!l || !r)return !l?r:l;
    if(l->pri > r->pri){
      l->rch = merge(l->rch,r);
      return update(l);
    }else{
      r->lch = merge(l,r->lch);
      return update(r);
    }
  }
  pair<node*,node*> split(node *t, ll k){
    if(!t) return make_pair<node*,node*>(NULL,NULL);
    if(k <= count(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-count(t->lch)-1);
      t->rch = s.first;
      return make_pair(update(t),s.second);
    }
  }
  ll __find(node *p,ll v){
    if(!p)return 0;
    if(p->val==v)return count(p->lch);
    return (p->val > v)?__find(p->lch,v):(count(p->lch)+1+__find(p->rch,v));
  }
  ll __less(node *p,ll v){
    if(!p)return 0;
    return (p->val >= v)?__less(p->lch,v):(count(p->lch)+1+__less(p->rch,v));
  }
  ll __less_eq(node *p,ll v){
    if(!p)return 0;
    return (p->val > v)?__less_eq(p->lch,v):(count(p->lch)+1+__less_eq(p->rch,v));
  }
  ll __get_at(node *p,ll k,ll acc){
    if(!p)return -1;
    ll lc=count(p->lch);
    if(acc+lc==k)return p->val;
    if(acc+lc>k)return __get_at(p->lch,k,acc);
    if(acc+lc<k)return __get_at(p->rch,k,acc+lc+1);
  }
public:
  void merge(Treap that){
    root = merge(root, that.root);
  }
  Treap split(ll k){
    Treap that;
    pair<node*,node*> p = split(root,k);
    root = p.first;
    that.root = p.second;
    return that;
  }
  void insert_at(ll v,ll k){
    pair<node*,node*> p = split(root,k);
    node* nn = new node(v);
    root = merge(p.first, nn);
    root = merge(root, p.second);
  }
  void erase_at(ll k){
    pair<node*,node*> p,q;
    q = split(root,k+1);
    p = split(q.first,k);
    root = merge(p.first, q.second);
  }
  void insert_by(ll v){
    insert_at(v,__less(root,v));
  }
  void erase_by(ll v){
    erase_at(__find(root,v));
  }
  ll count_less(ll v){
    return __less(root,v);
  }
  ll count_less_equal(ll v){
    return __less_eq(root,v);
  }
  ll get_at(ll k){
    return __get_at(root,k,0);
  }
  ll size(){
    return count(root);
  }
};

int main(){
  Treap tr;
  int q;
  scanf("%d",&q);
  ll add = 0ll;
  vl insrted;
  REP(tms,q){
    int t,x;
    scanf("%d%d",&t,&x);
    if(t==1){
      // insert
      tr.insert_by(x-add);
      insrted.push_back(x-add);
      // insrted[tms] = x-add;
    }else if(t==2){
      // delete
      ll v = insrted[x-1];
      tr.erase_by(v);
    }else if(t==3){
      // + x
      add += x;
    }
    // query
    ll low = 0ll;
    ll high = 100001ll;
    while(low + 1 < high){
      ll x = (low + high) / 2;
      ll cnt = tr.size() - tr.count_less(x-add);
      if(cnt >= x){
        low = x;
      }else{
        high = x;
      }
    }
    printf("%lld\n", low);
  }
  return 0;
}
0