This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int seg[1500000];
vector<int> stk[300100];
bool active[300100];
int get(int idx) {
if (stk[idx].empty()) return 0;
return stk[idx].back();
}
void update(int idx, int l, int r, int k) {
if (k < l || k >= r) return;
if (l + 1 == r) {
seg[idx] = get(l);
return;
}
int m = (l + r) >> 1;
update(idx * 2 + 1, l, m, k);
update(idx * 2 + 2, m, r, k);
seg[idx] = max(seg[idx * 2 + 1], seg[idx * 2 + 2]);
}
int query(int idx, int l, int r, int k) {
if (k <= l) return 0;
if (k >= r) return seg[idx];
int m = (l + r) >> 1;
return max(query(idx * 2 + 1, l, m, k), query(idx * 2 + 2, m, r, k));
}
int state[300100];
int par[300100];
int main() {
int n;
scanf("%d", &n);
int x,tmp;
for (int i = 1; i <= n; i++) par[i] = i;
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
if (x > 0) {
active[i] = true;
stk[0].push_back(i);
update(0, 0, n + 1, 0);
state[i] = x;
} else {
x = -x;
tmp = query(0, 0, n + 1, x);
tmp = par[tmp];
par[i] = tmp;
if (active[tmp]) stk[0].pop_back();
else stk[0].push_back(tmp);
active[tmp] = !active[tmp];
update(0, 0, n + 1, 0);
active[i] = true;
stk[x].push_back(i);
update(0, 0, n + 1, x);
}
printf("%d\n", state[get(0)]);
}
return 0;
}
Compilation message (stderr)
edi.cpp: In function 'int main()':
edi.cpp:40:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
edi.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |