| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 145094 |
2019-08-18T18:48:25 Z |
Vlatko |
Editor (BOI15_edi) |
C++14 |
|
222 ms |
33360 KB |
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 300010;
int n;
int level[maxn];
int eval[maxn]; // value for e
int uptr[maxn]; // e that u is pointing to
set<int> opidx[maxn]; // indexes at level
struct segtree {
int tree[4*maxn];
void build() {
memset(tree, -1, sizeof(tree));
}
void update(int v, int tl, int tr, int pos, int num) {
if (tl == tr) {
tree[v] = num;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm) {
update(2*v, tl, tm, pos, num);
} else {
update(2*v+1, tm+1, tr, pos, num);
}
tree[v] = max(tree[2*v], tree[2*v+1]);
}
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return -1;
if (l <= tl && tr <= r) return tree[v];
int tm = (tl + tr) / 2;
return max(query(2*v, tl, tm, l, min(r, tm)),
query(2*v+1, tm+1, tr, max(l, tm+1), r));
}
} tree; // max idx of active operation in this range of levels
void process_edit(int i, int x) {
// cout << "edit: "; debug(i, x);
eval[i] = x;
uptr[i] = -1;
opidx[0].insert(i);
tree.update(1, 0, n, 0, i);
}
void process_undo(int i, int lvl) {
int j = tree.query(1, 0, n, 0, lvl-1);
// cout << "undo: "; debug(i, lvl, j, level[j]);
eval[i] = -1;
level[i] = lvl;
if (level[j] == 0) {
// edit operation
uptr[i] = j;
opidx[0].erase(j);
tree.update(1, 0, n, 0, *prev(opidx[0].end()));
opidx[lvl].insert(i);
tree.update(1, 0, n, lvl, i);
} else {
// undo operation, pointing to edit operation
int k = uptr[j];
uptr[i] = uptr[j] = -1;
bool should_update = *prev(opidx[level[j]].end()) == j;
opidx[level[j]].erase(j);
if (should_update) {
tree.update(1, 0, n, level[j], opidx[level[j]].empty() ? -1 : *prev(opidx[level[j]].end()));
}
opidx[0].insert(k);
if (*prev(opidx[0].end()) == k) {
tree.update(1, 0, n, 0, k);
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
tree.build();
process_edit(0, 0);
for (int i = 1; i <= n; ++i) {
int a;
cin >> a;
if (a > 0) {
process_edit(i, a);
} else {
process_undo(i, -a);
}
cout << eval[tree.query(1, 0, n, 0, 0)] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
33360 KB |
Output is correct |
| 2 |
Correct |
218 ms |
33176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
159 ms |
26016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
