結果

問題 No.618 labo-index
コンテスト
ユーザー okaduki
提出日時 2017-12-19 01:17:02
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,527 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,900 ms
コンパイル使用メモリ 170,992 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-16 01:02:19
合計ジャッジ時間 6,821 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const LL INF = 1e18;

const int MAX_SEG = 16;//1<<17; // 131072
class LazySegT{
public:
  struct Node{
	LL mn;
	LL lazy_s;
	LL mx;
  };
  Node segT[2*MAX_SEG];

  LazySegT(int N){
	for(int i=0;i<2*MAX_SEG;++i){
	  segT[i].mn = -INF;
	  segT[i].mx = -INF;
	  segT[i].lazy_s = 0;
	}
  }

  void update(int k){
	segT[k].mn = min(segT[k*2+1].mn, segT[k*2+2].mn);
	segT[k].mx = max(segT[k*2+1].mx, segT[k*2+2].mx);
  }

  void put(int k, LL delta, LL len){
	segT[k].lazy_s += delta;
	segT[k].mn += delta;
	segT[k].mx += delta;
  }

  void eval(int k, int l, int r){
	if(segT[k].lazy_s){
	  if(k < MAX_SEG-1){
		segT[k].mn += segT[k].lazy_s;
		segT[k].mx += segT[k].lazy_s;
		
		put(2*k+1, segT[k].lazy_s, (r-l)/2);
		put(2*k+2, segT[k].lazy_s, (r-l)/2);
	  }
	  segT[k].lazy_s = 0;
	}
  }

  // dat[i] += c, a <= i < b
  void add(int a, int b, LL c, int k=0, int l=0, int r=MAX_SEG){
	eval(k,l,r);
	if(r <= a || b <= l) return;

	if(a <= l && r <= b){
	  put(k, c, r-l);
	  eval(k,l,r);
	}
	else{
	  add(a, b, c, k*2+1, l, (l+r)/2);
	  add(a, b, c, k*2+2, (l+r)/2, r);
	  update(k);
	}
  }

  void set(int i, LL c, int k=0, int l=0, int r=MAX_SEG){
	eval(k,l,r);
	if(r-l == 1){
	  segT[k].mn = segT[k].mx = c;
	}
	else{
	  int m = (l+r)/2;
	  if(i < m)
		set(i, c, k*2+1, l, m);
	  else
		set(i, c, k*2+2, m, r);
	  update(k);
	}
  }

  int query_aux(int a, int b, LL x, int k=0, int l=0, int r=MAX_SEG){
	eval(k, l, r);
	if(r <= a || b <= l) return 0;
	if(x <= segT[k].mn){
	  return min(b,r) - max(a,l);
	}
	if(segT[k].mx < x){
	  return 0;
	}

	int vl = query_aux(a, b, x, k*2+1, l, (l+r)/2);
	int vr = query_aux(a, b, x, k*2+2, (l+r)/2, r);
	update(k);
	return vl+vr;
  }

  int query(int a, int b, int ub){
	int lb = 0;
	while(ub-lb > 1){
	  int m = (lb + ub) / 2;
	  int x = query_aux(a, b, m);
	  if(m <= x)
		lb = m;
	  else
		ub = m;
	}

	return lb;
  }

  void debug(int k=0, int l=0, int r=MAX_SEG){
	eval(k,l,r);
	if(r-l == 1){
	  if(segT[k].mn == -INF)
		cout <<"-inf ";
	  else
		cout << segT[k].mn << " ";
	  return;
	}
	debug(k*2+1, l, (l+r)/2);
	debug(k*2+2, (l+r)/2, r);
  }
};

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int Q;
  cin >> Q;
  LazySegT seg(Q+1);
  int ix = 0;
  REP(q,Q){
	int t, x;
	cin >> t >> x;
	if(t == 1){
	  seg.set(ix++, x);
	}
	else if(t == 2){
	  seg.set(x-1, -INF);
	}
	else{
	  seg.add(0, ix, x);
	}

	cout << seg.query(0, ix, ix+1) << endl;
	//seg.debug();	cout<<endl;
  }

  return 0;
}
0