結果

問題 No.618 labo-index
ユーザー rickythetarickytheta
提出日時 2017-12-18 00:09:43
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,287 bytes
コンパイル時間 1,833 ms
コンパイル使用メモリ 173,972 KB
実行使用メモリ 14,592 KB
最終ジャッジ日時 2024-12-15 23:19:10
合計ジャッジ時間 7,385 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 323 ms
14,592 KB
testcase_35 AC 291 ms
14,464 KB
testcase_36 AC 111 ms
9,088 KB
testcase_37 AC 245 ms
8,960 KB
testcase_38 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
  map<int, ll> insrted;
  REP(tms,q){
    int t,x;
    scanf("%d%d",&t,&x);
    if(t==1){
      // insert
      tr.insert_by(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 = 100000000000000ll;
    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