#include "wall.h" #include<bits/stdc++.h> using namespace std; int n; vector<int>ans; struct seg{ int mn,mx,l,r; seg *lf,*rg; void build(int x,int y){ l=x,r=y; mn=mx=0; if(l==r){ return; } int mid=(l+r)/2; lf=new seg(),rg=new seg(); lf->build(l,mid),rg->build(mid+1,r); } void apply(int mini,int maxi){ mn=min(max(mn,mini),maxi); mx=max(min(mx,maxi),mini); } void prop(){ if(l==r)return; lf->apply(mn,mx),rg->apply(mn,mx); } void update(int posl,int posr,int op,int brp){ if(l>posr || r<posl)return; if(l>=posl && r<=posr){ if(op==1){ mn=max(mn,brp); mx=max(mx,brp); } else{ mn=min(mn,brp); mx=min(mx,brp); } return; } prop(); lf->update(posl,posr,op,brp),rg->update(posl,posr,op,brp); mn=min(lf->mn,rg->mn); mx=max(lf->mx,rg->mx); } void solve(int l,int r){ if(l==r){ ans[l]=mn; return; } prop(); int mid=(l+r)/2; lf->solve(l,mid),rg->solve(mid+1,r); } }; void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ n=N; ans=vector<int>(n+1,0); seg apa; apa.build(0,n-1); for(int q=0;q<k;q++){ apa.update(left[q],right[q],op[q],height[q]); } apa.solve(0,n-1); for(int q=0;q<n;q++){ finalHeight[q]=ans[q]; } return; }