| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 838682 | fanwen | Weighting stones (IZhO11_stones) | C++17 | 2 ms | 1364 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.
/**
* author : pham van sam
* created : 27 August 2023 (Sunday)
**/
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct node {
T Max, Min;
node(T Max = 0, T Min = 0) : Max(Max), Min(Min){}
friend node operator + (const node &lhs, const node &rhs) {
return node(max(lhs.Max, rhs.Max), min(lhs.Min, rhs.Min));
}
};
template <class T>
struct lazy_segment_tree {
vector <node <T>> it;
vector <T> lazy;
int n, version = 0;
void modify(int idx, int l, int r, T val) {
lazy[idx] += val;
it[idx].Max += val;
it[idx].Min += val;
}
void push(int idx, int l, int r) {
if(lazy[idx] == 0) return;
int mid = l + r >> 1;
modify(idx << 1, l, mid, lazy[idx]);
modify(idx << 1 | 1, mid + 1, r, lazy[idx]);
lazy[idx] = 0;
}
void update(int idx, int l, int r, int u, int v, T val) {
if(l > v || r < u) return;
if(l >= u && r <= v) {
modify(idx, l, r, val);
return;
}
push(idx, l, r);
int mid = l + r >> 1;
update(idx << 1, l, mid, u, v, val);
update(idx << 1 | 1, mid + 1, r, u, v, val);
it[idx] = it[idx << 1] + it[idx << 1 | 1];
}
node<T> get(int idx, int l, int r, int u, int v) {
if(l > v || r < u) return node<T>(-n - 1, n + 1);
if(l >= u && r <= v) return it[idx];
push(idx, l, r);
int mid = l + r >> 1;
return get(idx << 1, l, mid, u, v) + get(idx << 1 | 1, mid + 1, r, u, v);
}
int find(int idx, int l, int r) {
push(idx, l, r);
if(it[idx].Max == 0 && it[idx].Min == 0) return -1;
if(l == r) return l;
int mid = l + r >> 1;
if(it[idx << 1 | 1].Max != 0 || it[idx << 1 | 1].Min != 0) return find(idx << 1 | 1, mid + 1, r);
return find(idx << 1, l, mid);
}
public :
explicit lazy_segment_tree(int n) :
n(n), lazy(n << 2 | 1, 0), it(n << 2 | 1) {}
void update(int l, int r, T val) {
update(1, 1, n, l, r, val);
}
node<T> get(int l, int r) {
return get(1, 1, n, l, r);
}
T get(int u) {
return get(u, u).Max;
}
int find() {
++version;
return find(1, 1, n);
}
};
void you_make_it(void) {
int n; cin >> n;
lazy_segment_tree <int> it(n);
for (int i = 1; i <= n; ++i) {
int x, r; cin >> x >> r;
it.update(1, x, (r == 1 ? 1 : -1));
int res = it.find();
if(res == -1) {
cout << "?\n";
continue;
}
// cout << "i " << res << '\n';
// cout << "Max " << it.get(1, n).Max << '\n';
// cout << "Min " << it.get(1, n).Min << '\n';
// cout << it.get(3) << '\n';
if(it.get(res) > 0) {
cout << (it.get(1, n).Min >= 0 ? ">" : "?");
} else {
cout << (it.get(1, n).Max <= 0 ? "<" : "?");
}
cout << endl;
}
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||