#include <>
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK ""
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 7;
int ans[N];
int n, k;
struct IntervalTree {
int n;
int st[N];
pair <int, int> lazy[N];
IntervalTree(int n) {
this -> n = n;
for (int i = 0; i <= 4 * n; ++i) lazy[i] = mp(-INT_MAX, INT_MAX);
}
void fix(int id, int l, int r, int type) {
if (type == 0)
mini(st[id], lazy[id].se);
else
maxi(st[id], lazy[id].fi);
if (l < r) {
if (type == 1) {
mini(lazy[id << 1].fi, lazy[id].se);
mini(lazy[id << 1].se, lazy[id].se);
mini(lazy[id << 1 | 1].fi, lazy[id].se);
mini(lazy[id << 1 | 1].se, lazy[id].se);
} else {
maxi(lazy[id << 1].fi, lazy[id].fi);
maxi(lazy[id << 1].se, lazy[id].fi);
maxi(lazy[id << 1 | 1].fi, lazy[id].fi);
maxi(lazy[id << 1 | 1].se, lazy[id].fi);
}
}
}
void update(int u, int v, int h, int type, int id = 1, int l = 1, int r = -1) {
if (r < 0) r = n;
fix(id, l, r, 0);
fix(id, l, r, 1);
if (l > v || r < u) return;
if (u <= l && r <= v) {
if (type == 0) {
mini(lazy[id].fi, h);
mini(lazy[id].se, h);
} else {
maxi(lazy[id].fi, h);
maxi(lazy[id].se, h);
}
fix(id, l, r, type);
return;
}
int mid = l + r >> 1;
update(u, v, h, type, id << 1, l, mid);
update(u, v, h, type, id << 1 | 1, mid + 1, r);
}
void get(int id = 1, int l = 1, int r = -1) {
if (r < 0) r = n;
if (l == r) {
ans[l] = st[id];
return;
}
int mid = l + r >> 1;
get(id << 1, l, mid);
get(id << 1 | 1, mid + 1, r);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
IntervalTree IT(n);
for (int i = 1; i <= k; ++i) {
IT.update(left[i] + 1, right[i] + 1, height[i], op[i]);
}
IT.get();
for (int i = 1; i <= n; ++i) {
finalHeight[i - 1] = ans[i];
}
}
// int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cin >> n >> k;
// IntervalTree IT(n);
// cout << n << "\n";
// for (int i = 1; i <= k; ++i) {
// int op, l, r, h; cin >> op >> l >> r >> h;
// IT.update(l + 1, r + 1, h, op);
// }
// IT.get();
// for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
// }
Compilation message
wall.cpp:1:10: error: empty filename in #include
1 | #include <>
| ^~
wall.cpp: In member function 'void IntervalTree::update(int, int, int, int, int, int, int)':
wall.cpp:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int mid = l + r >> 1;
| ~~^~~
wall.cpp: In member function 'void IntervalTree::get(int, int, int)':
wall.cpp:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int mid = l + r >> 1;
| ~~^~~
