1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| const int N = 300005;
class segtree{
private:
struct{int l,r,v;} tr[N*30];
int root[N],idx;
void pushup(int u){tr[u].v = min(tr[tr[u].l].v,tr[tr[u].r].v);}
public:
segtree(){tr[0].v=1e9;}
int& operator [](const int &x){return root[x];}
void modify(int &u,int l,int r,int p,int v){
tr[++idx] = tr[u];
u = idx;
if(l==r){
tr[u].v = v;
return;
}
int mid = (l+r)>>1;
if(p<=mid)
modify(tr[u].l,l,mid,p,v);
else
modify(tr[u].r,mid+1,r,p,v);
pushup(u);
}
int query(int u,int l,int r,int p){
if(l==r)
return l;
int mid = (l+r)>>1;
if(!tr[u].r||tr[tr[u].r].v>=p)
return query(tr[u].l,l,mid,p);
return query(tr[u].r,mid+1,r,p);
}
}tr;
int ans[N];
int n;
int main(){
n = in;
for(int k=1;k<=n;k++){
int x = in;
if(x>0){
tr[k] = tr[k-1];
ans[k] = x;
tr.modify(tr[k],1,n,k,0);
}
else{
int p = tr.query(tr[k-1],1,n,-x);
tr[k] = tr[p-1];
ans[k] = ans[p-1];
tr.modify(tr[k],1,n,k,-x);
}
out(ans[k],'\n');
}
return 0;
}
|