/**
* 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) {
if(it[idx].Max == 0 && it[idx].Min == 0) return -1;
if(l == r) return l;
push(idx, l, r);
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;
}
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
stones.cpp: In instantiation of 'lazy_segment_tree<T>::lazy_segment_tree(int) [with T = int]':
stones.cpp:94:30: required from here
stones.cpp:23:9: warning: 'lazy_segment_tree<int>::n' will be initialized after [-Wreorder]
23 | int n, version = 0;
| ^
stones.cpp:22:13: warning: 'std::vector<int> lazy_segment_tree<int>::lazy' [-Wreorder]
22 | vector <T> lazy;
| ^~~~
stones.cpp:71:14: warning: when initialized here [-Wreorder]
71 | explicit lazy_segment_tree(int n) :
| ^~~~~~~~~~~~~~~~~
stones.cpp:22:13: warning: 'lazy_segment_tree<int>::lazy' will be initialized after [-Wreorder]
22 | vector <T> lazy;
| ^~~~
stones.cpp:21:20: warning: 'std::vector<node<int>, std::allocator<node<int> > > lazy_segment_tree<int>::it' [-Wreorder]
21 | vector <node <T>> it;
| ^~
stones.cpp:71:14: warning: when initialized here [-Wreorder]
71 | explicit lazy_segment_tree(int n) :
| ^~~~~~~~~~~~~~~~~
stones.cpp: In instantiation of 'void lazy_segment_tree<T>::update(int, int, int, int, int, T) [with T = int]':
stones.cpp:75:15: required from 'void lazy_segment_tree<T>::update(int, int, T) [with T = int]'
stones.cpp:97:39: required from here
stones.cpp:46:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid = l + r >> 1;
| ~~^~~
stones.cpp: In instantiation of 'int lazy_segment_tree<T>::find(int, int, int) [with T = int]':
stones.cpp:88:17: required from 'int lazy_segment_tree<T>::find() [with T = int]'
stones.cpp:98:24: required from here
stones.cpp:64:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | int mid = l + r >> 1;
| ~~^~~
stones.cpp: In instantiation of 'node<T> lazy_segment_tree<T>::get(int, int, int, int, int) [with T = int]':
stones.cpp:79:19: required from 'node<T> lazy_segment_tree<T>::get(int, int) [with T = int]'
stones.cpp:104:27: required from here
stones.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | int mid = l + r >> 1;
| ~~^~~
stones.cpp: In instantiation of 'void lazy_segment_tree<T>::push(int, int, int) [with T = int]':
stones.cpp:45:9: required from 'void lazy_segment_tree<T>::update(int, int, int, int, int, T) [with T = int]'
stones.cpp:75:15: required from 'void lazy_segment_tree<T>::update(int, int, T) [with T = int]'
stones.cpp:97:39: required from here
stones.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
2 ms |
340 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
340 KB |
Output is correct |
| 10 |
Correct |
15 ms |
780 KB |
Output is correct |
| 11 |
Correct |
103 ms |
3380 KB |
Output is correct |
| 12 |
Correct |
138 ms |
5380 KB |
Output is correct |
| 13 |
Correct |
147 ms |
5984 KB |
Output is correct |
| 14 |
Correct |
166 ms |
5892 KB |
Output is correct |
| 15 |
Correct |
146 ms |
5924 KB |
Output is correct |
| 16 |
Correct |
153 ms |
5960 KB |
Output is correct |
| 17 |
Correct |
151 ms |
5980 KB |
Output is correct |
| 18 |
Correct |
153 ms |
6008 KB |
Output is correct |
| 19 |
Correct |
149 ms |
5968 KB |
Output is correct |
| 20 |
Correct |
157 ms |
5968 KB |
Output is correct |
| 21 |
Correct |
146 ms |
5944 KB |
Output is correct |
| 22 |
Correct |
162 ms |
5984 KB |
Output is correct |
| 23 |
Correct |
152 ms |
5964 KB |
Output is correct |
| 24 |
Correct |
162 ms |
5960 KB |
Output is correct |
| 25 |
Correct |
150 ms |
6052 KB |
Output is correct |
