# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
993163 | tch1cherin | Weighting stones (IZhO11_stones) | C++17 | 68 ms | 5464 KiB |
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 <bits/stdc++.h>
using namespace std;
struct segment_tree {
struct node {
int value, push;
};
node merge(node a, node b) {
return {min(a.value, b.value), 0};
}
int size;
vector<node> tree;
void apply(int x, int value) {
tree[x].value += value;
tree[x].push += value;
}
void propagate(int x) {
if (tree[x].push != 0) {
apply(x * 2, tree[x].push);
apply(x * 2 + 1, tree[x].push);
tree[x].push = 0;
}
}
segment_tree(int n) : size(2 << __lg(n)) {
tree.assign(size * 2, {0, 0});
}
void update(int l, int r, int value) {
update(l, r, value, 1, 0, size);
}
void update(int l, int r, int value, int x, int lx, int rx) {
if (lx >= r || rx <= l) {
return;
} else if (lx >= l && rx <= r) {
apply(x, value);
} else {
propagate(x);
int mid = (lx + rx) / 2;
update(l, r, value, x * 2, lx, mid);
update(l, r, value, x * 2 + 1, mid, rx);
tree[x] = merge(tree[x * 2], tree[x * 2 + 1]);
}
}
int query() {
return tree[1].value;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N;
cin >> N;
segment_tree T1(N), T2(N);
for (int i = 0; i < N; i++) {
int R, S;
cin >> R >> S;
if (S == 1) {
T1.update(0, R, 1);
T2.update(0, R, -1);
} else {
T1.update(0, R, -1);
T2.update(0, R, 1);
}
if (T1.query() >= 0) {
cout << ">\n";
} else if (T2.query() >= 0) {
cout << "<\n";
} else {
cout << "?\n";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |