#include <stdio.h>
#include "wall.h"
struct str{
int left;
int right;
}x[5000010],check[5000010];
int max(int a, int b)
{
return a>b?a:b;
}
int min(int a, int b)
{
return a<b?a:b;
}
void func(int k, int left, int right, int h_lower, int h_upper)
{
if(x[k].right<left) return;
if(x[k].left>right) return;
if(left<=x[k].left&&x[k].right<=right)
{
if(check[k].right<h_lower) check[k]={h_lower,h_lower};
else if(check[k].left>h_upper) check[k]={h_upper,h_upper};
else check[k]={max(check[k].left,h_lower),min(check[k].right,h_upper)};
return;
}
func(2*k,x[2*k].left,x[2*k].right,check[k].left,check[k].right);
func(2*k+1,x[2*k+1].left,x[2*k+1].right,check[k].left,check[k].right);
check[k]={0,100000};
func(2*k,left,right,h_lower,h_upper);
func(2*k+1,left,right,h_lower,h_upper);
}
int find(int k)
{
str a={0,100000};
while(k)
{
if(check[k].right<a.left) a={check[k].right,check[k].right};
else if(check[k].left>a.right) a={check[k].left,check[k].left};
else a={max(check[k].left,a.left),min(check[k].right,a.right)};
k/=2;
}
return a.left;
}
void buildWall(int n, int k, int op[],int left[],int right[], int height[],int finalheight[])
{
int C,i,a,b,L,R;
for(C=1;C<n;C*=2);
for(i=C;i<2*C;i++) x[i]={i,i},check[i]={0,0};
for(i=C-1;i>=1;i--)
{
x[i]={x[2*i].left,x[2*i+1].right};
check[i]={0,100000};
}
for(i=0;i<k;i++)
{
a=op[i];
b=height[i];
L=left[i];
R=right[i];
if(a==1) func(1,C+L,C+R,b,100000);
else func(1,C+L,C+R,0,b);
//func(1,C+L,C+R,a,b);
//for(int j=0;j<n;j++)
//{
//printf("%d : %d\n",j,find(j+C));
//}
//printf("-------------------------\n");
}
for(i=0;i<n;i++)
{
finalheight[i]=find(i+C);
//printf("%d : %d\n",i,finalheight[i]);
}
}
/*int x1[110],x2[110],x3[110],x4[110],y[110];
int main()
{
int a,b,i;
scanf("%d%d",&a,&b);
for(i=0;i<b;i++)
{
scanf("%d%d%d%d",&x1[i],&x2[i],&x3[i],&x4[i]);
}
buildWall(a,b,x1,x2,x3,x4,y);
}*/
