#include "wall.h" #include <bits/stdc++.h> using namespace std; struct LazySeg { vector<pair<int, int>> seg; vector<pair<int, int>> lazy; int sz; pair<int, int> comb(pair<int, int> s1, pair<int, int> s2){ return {min(s1.first, s2.first), max(s1.second, s2.second)}; } LazySeg(int size){ sz = size; lazy.resize(4*sz, {0, INT_MAX}); seg.resize(4*sz, {0, INT_MAX}); } void push(int n){ seg[n].first = min(lazy[n].second, max(seg[n].first, lazy[n].first)); seg[n].second = max(lazy[n].first, min(seg[n].second, lazy[n].second)); if(2*n+1 < 4*sz){ lazy[2*n].first = min(lazy[n].second, max(lazy[2*n].first, lazy[n].first)); lazy[2*n].second = max(lazy[n].first, min(lazy[2*n].second, lazy[n].second)); lazy[2*n+1].first = min(lazy[n].second, max(lazy[2*n+1].first, lazy[n].first)); lazy[2*n+1].second = max(lazy[n].first, min(lazy[2*n+1].second, lazy[n].second)); } lazy[n] = {0, INT_MAX}; } void __update(int n, int l, int r, int left, int right, int val, bool type){ // type 0 -> Add, type 1 -> Delete push(n); if(l > right || r < left) return; if(l >= left && r <= right){ if(type){ lazy[n].second = val; } else{ lazy[n].first = val; } push(n); return; } int m = (l+r)/2; __update(2*n, l, m, left, right, val, type); __update(2*n+1, m+1, r, left, right, val, type); } void update(int left, int right, int val, bool type) { __update(1, 1, sz, left, right, val, type); } void answer(int n, int l, int r, int ans[]){ push(n); if(l == r){ ans[l-1] = seg[n].first; return; } int m = (l+r)/2; answer(2*n, l, m, ans); answer(2*n+1, m+1, r, ans); } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ LazySeg seg(n); for(int i=0;i<k;i++){ seg.update(left[i]+1, right[i]+1, height[i], op[i]-1); } seg.answer(1, 1, n, finalHeight); }