8VC Venture Cup 2017 - Final Round C. Nikita and stack

#include<bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define eps 1e-2
#define gcd __gcd
#define pb push_back
#define PI acos(-1.0)
#define lowbit(x) (x)&(-x)
#define bug printf("!!!!!\n");
#define mem(x,y) memset(x,y,sizeof(x))

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;
typedef unsigned long long uLL;

const int maxn = 1e5+2;
const int INF  = 1<<30;
const int mod  = 1e9+7;

const int N=1e5+10;
struct node{
    
    ll l,r,mx,lazy;
}tr[N<<2];
ll t,n,Q,a[N];

void pushup(ll x){
    
    tr[x].mx=max(tr[x<<1].mx,tr[x<<1|1].mx);
}
void pushdown(ll x){
    
    if(tr[x].lazy){
    
        tr[x<<1].mx+=tr[x].lazy;
        tr[x<<1|1].mx+=tr[x].lazy;
        tr[x<<1].lazy+=tr[x].lazy;
        tr[x<<1|1].lazy+=tr[x].lazy;
        tr[x].lazy=0;
    }
}
void build(ll p,ll l,ll r){
    
    tr[p].l=l;tr[p].r=r;
    if(l==r) return ;
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    pushup(p);
}
void update(ll p,ll l,ll r,ll val){
    
    // cout<<tr[p].l<<" "<<tr[p].r<<" "<<l<<" "<<r<<endl;
    if(tr[p].l>=l&&tr[p].r<=r){
    
        tr[p].lazy+=val;
        tr[p].mx+=val;
        // if(tr[p].l==1) cout<<tr[p].mx<<" "<<val<<endl;
        return ;
    }
    pushdown(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(mid>=l) update(p<<1,l,r,val);
    if(mid+1<=r) update(p<<1|1,l,r,val);
    pushup(p);
}

ll query(int p){
    
    if(tr[p].l==tr[p].r){
    
        if(tr[p].mx<=0) return -1;
        else return a[tr[p].l];
    }
    ll mid=(tr[p].l+tr[p].r)>>1;
    pushdown(p);
    int res=0;
    if(tr[p<<1|1].mx>0) res=query(p<<1|1);
    else res=query(p<<1);
    pushup(p);
    return res;
}


void solve(){
    
    int m;scanf("%d",&m);
    build(1,1,N);
    // cout<<tr[3].l<<" "<<tr[3].r<<endl;
    while(m--){
    
        int op,x,y;scanf("%d%d",&x,&op);
        if(op==1){
    
            scanf("%d",&y);
            update(1,1,x,1);a[x]=y;
        }else{
    
            update(1,1,x,-1);
        }
        // cout<<tr[1].mx<<endl;
        printf("%lld\n",query(1));
    }
    
    return;
}

int main()
{
    
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// ios::sync_with_stdio(false);
    int t = 1;
    //scanf("%d",&t);
    while(t--){
    
    // printf("Case %d: ",cas++);
        solve();
    }
    return 0;
}