#include <iostream>
#include <stdio.h>
#include "wall.h"
//#include "grader.cpp"
using namespace std;
const int mxn = 8e6 + 10,mxi = 1e7 + 10;
struct we
{
int bb,ub;
};
struct we se[mxn] = {};
int ban[mxn] = {};
int fimi(int l,int r)
{
if(l < r)
return l;
return r;
}
int fima(int l,int r)
{
if(l > r)
return l;
return r;
}
int cre(int cl,int cr,int no)
{
if(cl == cr)
{
se[no] = {0,0};
return 0;
}
int mid = (cl+cr) / 2;
se[no] = {0,mxi};
cre(cl,mid,no*2);
cre(mid+1,cr,no*2+1);
return 0;
}
int ins(int cl,int cr,int no,int tl,int tr,int iva,int uob,int dob,int dou)
{
if(cr < tl || cl > tr)
{
if(dob > se[no].ub)
{
se[no].bb = dob;
se[no].ub = dob;
}
else if(dou < se[no].bb)
{
se[no].bb = dou;
se[no].ub = dou;
}
else
{
se[no].bb = fima(dob,se[no].bb);
se[no].ub = fimi(dou,se[no].ub);
}
return 0;
}
if(cl >= tl && cr <= tr)
{
if(dob > se[no].ub)
{
se[no].bb = dob;
se[no].ub = dob;
}
else if(dou < se[no].bb)
{
se[no].bb = dou;
se[no].ub = dou;
}
else
{
se[no].bb = fima(dob,se[no].bb);
se[no].ub = fimi(dou,se[no].ub);
}
// se[no].bb = fima(dob,se[no].bb);
// se[no].ub = fimi(dou,se[no].ub);
if(uob == 1)
{
if(iva > se[no].ub)
{
se[no].bb = iva;
se[no].ub = iva;
}
else
{
se[no].bb = fima(iva,se[no].bb);
}
}
else
{
if(iva < se[no].bb)
{
se[no].bb = iva;
se[no].ub = iva;
}
else
{
se[no].ub = fimi(iva,se[no].ub);
}
}
return 0;
}
int mid = (cl+cr) / 2;
if(dob > se[no].ub)
{
dou = dob;
}
else if(dou < se[no].bb)
{
dob = dou;
}
else
{
dob = fima(dob,se[no].bb);
dou = fimi(dou,se[no].ub);
}
se[no].bb = 0;
se[no].ub = mxi;
ins(cl,mid,no*2,tl,tr,iva,uob,dob,dou);
ins(mid+1,cr,no*2+1,tl,tr,iva,uob,dob,dou);
return 0;
}
int las(int cl,int cr,int no,int dob,int dou)
{
if(cl == cr)
{
if(dob > se[no].ub)
{
se[no].bb = dob;
se[no].ub = dob;
}
else if(dou < se[no].bb)
{
se[no].bb = dou;
se[no].ub = dou;
}
else
{
se[no].bb = fima(dob,se[no].bb);
se[no].ub = fimi(dou,se[no].ub);
}
ban[cl] = se[no].bb;
return 0;
}
int mid = (cl+cr) / 2;
if(dob > se[no].ub)
{
dou = dob;
}
else if(dou < se[no].bb)
{
dob = dou;
}
else
{
dob = fima(dob,se[no].bb);
dou = fimi(dou,se[no].ub);
}
se[no].bb = dob;
se[no].ub = dou;
las(cl,mid,no*2,dob,dou);
las(mid+1,cr,no*2+1,dob,dou);
return 0;
}
void buildWall(int n, int k, int op[], int le[], int ri[], int ahei[], int ans[])
{
int i,j;
cre(0,n-1,1);
for(i=0; i<k; i++)
{
ins(0,n-1,1,le[i],ri[i],ahei[i],op[i],0,mxi);
}
las(0,n-1,1,0,mxi);
for(i=0; i<n; i++)
{
ans[i] = ban[i];
}
return;
}
//int main()
//{
// cout << "Hello world!" << endl;
// return 0;
//}
