Codeforces Round #393 (Div. 2) (8VC Venture Cup 2017 - Final Round Div. 2 Edition) E - Nikita and stack 线段树好题

http://codeforces.com/contest/760/problem/E

```#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>

using namespace std;

const int N = 1e5 + 7;
const int M = 1e6 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +7;

int n, lazy[N << 2], mx[N << 2], a[N];

void pushDown(int rt) {
if(!lazy[rt]) return;
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
mx[rt << 1] += lazy[rt];
mx[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
}

void update(int L, int R, int v, int l, int r, int rt) {
if(l >= L && r <= R) {
mx[rt] += v;
lazy[rt] += v;
return;
}

int mid = l + r >> 1;
pushDown(rt);

if(L <= mid) update(L, R, v, l, mid, rt << 1);
if(R > mid) update(L, R, v, mid + 1, r, rt << 1 | 1);
mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}

int query(int l, int r, int rt) {

if(mx[rt] <= 0) return -1;
if(l == r) return l;
int mid = l + r >> 1;
pushDown(rt);
if(mx[rt << 1 | 1] > 0) return query(mid + 1, r, rt << 1 | 1);

else return query(l, mid, rt << 1);
}

int main(){
scanf("%d", &n);
int T = n;
while(T--) {
int op, id, x;
scanf("%d%d", &id, &op);
if(op == 1) {
scanf("%d", &x);
a[id] = x;
update(1, id, 1, 1, n, 1);
} else {
update(1, id, -1, 1, n, 1);
}

int idx = query(1, n, 1);
if(idx == -1) puts("-1");
else printf("%d\n", a[idx]);
}
return 0;
}

/*
*/```

Codeforces Round #393 (Div. 2) (8VC Venture Cup 2017 - Final Round Div. 2 Edition) E - Nikita and stack 线段树好题

(0)
(0)

0条