#include "wall.h" #include <bits/stdc++.h> using namespace std; #define pii pair<int,int> const int inf = 1e5; pii st[1<<22]; int arr[1<<21]; void apply(int i, pii qu){ if(qu.first==-1) return; if(st[i].first==-1){st[i]=qu; return;} if(st[i].second <= qu.first) st[i] = {qu.first,qu.first}; else if(st[i].first >= qu.second) st[i] = {qu.second,qu.second}; else st[i] = {max(st[i].first,qu.first),min(st[i].second,qu.second)}; } void push(int i){ apply(i<<1,st[i]); apply(i<<1|1,st[i]); st[i] = {-1,-1}; } void update(int i, int l, int r, int s, int e, pii qu){ if(r < s || l > e) return; if(s <= l && r <= e){ apply(i,qu); return; } push(i); int m = (l+r)>>1; update(i<<1,l,m,s,e,qu); update(i<<1|1,m+1,r,s,e,qu); } void build(int i, int l, int r){ if(l==r){arr[l]=st[i].first; return;} int m = (l+r)>>1; push(i); build(i<<1,l,m); build(i<<1|1,m+1,r); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ st[1] = {0,0}; for(int i = 0; i < k; i++){ if(op[i]==1) update(1,0,n-1,left[i],right[i],{height[i],inf}); else update(1,0,n-1,left[i],right[i],{0,height[i]}); } build(1,0,n-1); for(int i = 0; i < n; i++) finalHeight[i] = arr[i]; return; }