#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int N;
int mini[8000007];
int maxi[8000007];
void add_mini(int node, int val)
{
if(val==-1)
{
return;
}
if(mini[node]==-1)
{
mini[node]=val;
}
mini[node]=max(mini[node],val);
if(maxi[node]!=-1)
{
maxi[node]=max(mini[node],maxi[node]);
}
}
void add_maxi(int node, int val)
{
if(val==-1)
{
return;
}
if(maxi[node]==-1)
{
maxi[node]=val;
}
maxi[node]=min(maxi[node],val);
if(mini[node]!=-1)
{
mini[node]=min(maxi[node],mini[node]);
}
}
void update_mini(int hl, int hr, int h, int node=1, int l=0, int r=N-1)
{
if(hl<=l && r<=hr)
{
add_mini(node,h);
return;
}
add_mini(node*2,mini[node]);
add_maxi(node*2,maxi[node]);
add_mini(node*2+1,mini[node]);
add_maxi(node*2+1,maxi[node]);
mini[node]=-1;
maxi[node]=-1;
int m=(l+r)/2;
if(hl<=m)
{
update_mini(hl,hr,h,node*2,l,m);
}
if(m+1<=hr)
{
update_mini(hl,hr,h,node*2+1,m+1,r);
}
}
void update_maxi(int hl, int hr, int h, int node=1, int l=0, int r=N-1)
{
if(hl<=l && r<=hr)
{
add_maxi(node,h);
return;
}
add_mini(node*2,mini[node]);
add_maxi(node*2,maxi[node]);
add_mini(node*2+1,mini[node]);
add_maxi(node*2+1,maxi[node]);
mini[node]=-1;
maxi[node]=-1;
int m=(l+r)/2;
if(hl<=m)
{
update_maxi(hl,hr,h,node*2,l,m);
}
if(m+1<=hr)
{
update_maxi(hl,hr,h,node*2+1,m+1,r);
}
}
int* res;
void last(int node=1, int l=0, int r=N-1)
{
if(l==r)
{
res[l]=mini[node];
return;
}
add_mini(node*2,mini[node]);
add_maxi(node*2,maxi[node]);
add_mini(node*2+1,mini[node]);
add_maxi(node*2+1,maxi[node]);
mini[node]=-1;
maxi[node]=-1;
last(node*2,l,(l+r)/2);
last(node*2+1,(l+r)/2+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
N=n;
res=finalHeight;
for(int i=0;i<k;i++)
{
if(op[i]==1)
{
update_mini(left[i],right[i],height[i]);
}
else
{
update_maxi(left[i],right[i],height[i]);
}
}
last();
return;
}
