#include <bits/stdc++.h> #include "wall.h" using namespace std; class SegmentTree { public: int size; vector<pair<int,int>> a; vector<pair<bool,int>> lazy; // pair item 1 : low operation // pair item 2 : high operation SegmentTree(int size) { size = size; for (int i = 0; i < (4*size)+1; i++) { a.push_back({0,0}); lazy.push_back({0,-1}); // lazy item 1 = operation type // lazy item 2 = k } } void update(int v, int coveredStart, int coveredEnd, int l, int r, bool op, int k) { /*V = current vertex | coveredStart = start of range covered by current vertex | coveredEnd = end of range covered by current vertex | l = left of query r = right of query | op = operation type [add/remove] | k = X for operation*/ // node lies entirely outside of desired range if (r < coveredStart || l > coveredEnd) { return; } // node lies entirely within desired range else if (coveredStart >= l && coveredEnd <= r) { if (op==0) { // ADD operation a[v].first=max(a[v].first,k); a[v].second=max(a[v].second,k); } else{ // REMOVE operation a[v].first=min(a[v].first,k); a[v].second=min(a[v].second,k); } if (coveredStart != coveredEnd) { lazy[v]={op,k}; } } // node lies partially within desired range else{ int mid = (coveredStart+coveredEnd)/2; if (lazy[v].second!=-1) { // propagate change downwards update(v*2,coveredStart,mid,coveredStart,mid,lazy[v].first,lazy[v].second); update((v*2)+1,mid+1,coveredEnd,mid+1,coveredEnd,lazy[v].first,lazy[v].second); lazy[v].second=-1; } // left child update(v*2,coveredStart,mid,l,r,op,k); // right child update((v*2)+1,mid+1,coveredEnd,l,r,op,k); } } int traverse(int v, int l, int r, int target) { // base case -> target found if (l==r && l == target) { return a[v].first; } // out of range else if (l > target || r < target) { return -1; } // partially in range else{ int mid = (l+r)/2; if (lazy[v].second != -1) { update(v*2,l,mid,l,mid,lazy[v].first,lazy[v].second); update((v*2)+1,mid+1,r,mid+1,r,lazy[v].first,lazy[v].second); lazy[v].second=-1; } int left = traverse(v*2,l,mid,target); int right = traverse((v*2)+1,mid+1,r,target); return max(left,right); } } }; void buildWall(int n, int k, int op[], int left[],int right[], int height[], int finalHeight[]) { SegmentTree segTree = SegmentTree(n); for (int i = 0; i < k; i++) { int l = left[i]; int r = right[i]; int operation = op[i]-1; int h = height[i]; segTree.update(1,0,n-1,l,r,operation,h); } for (int i = 0; i < k; i++) { finalHeight[i] = segTree.traverse(1,0,n-1,i); } }