#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
struct som {
int debInter,finInter,minInter,maxInter;
};
const int TAILLE_MAX=(1<<21),INFINI=1000*1000*1000;
int nbVal,nbReq;
som lazy[2*TAILLE_MAX];
void pushFlag(int pos) {
if (lazy[pos].debInter!=lazy[pos].finInter) {
for (int j=0;j<2;j++) {
if (lazy[2*pos+j].maxInter<lazy[pos].minInter) {
lazy[2*pos+j].minInter=lazy[pos].minInter;
lazy[2*pos+j].maxInter=lazy[pos].minInter;
}
else if (lazy[2*pos+j].minInter>lazy[pos].maxInter) {
lazy[2*pos+j].minInter=lazy[pos].maxInter;
lazy[2*pos+j].maxInter=lazy[pos].maxInter;
}
else {
lazy[2*pos+j].minInter=max(lazy[2*pos+j].minInter,lazy[pos].minInter);
lazy[2*pos+j].maxInter=min(lazy[2*pos+j].maxInter,lazy[pos].maxInter);
}
}
lazy[pos].minInter=0;
lazy[pos].maxInter=INFINI;
}
}
void init(int pos,int deb,int fin) {
lazy[pos].debInter=deb;
lazy[pos].finInter=fin;
//cout<<pos<<" "<<deb<<" "<<fin<<endl;
if (deb!=fin) {
int mid=(deb+fin)/2;
init(2*pos,deb,mid);
init(2*pos+1,mid+1,fin);
}
}
void modif(int pos,int deb,int fin,int typeModif,int valModif) {
if (lazy[pos].debInter>fin or lazy[pos].finInter<deb) {
pushFlag(pos);
}
else if (lazy[pos].debInter>=deb and lazy[pos].finInter<=fin) {
if (typeModif==1) {
lazy[pos].minInter=max(lazy[pos].minInter,valModif);
lazy[pos].maxInter=max(lazy[pos].maxInter,valModif);
}
else {
lazy[pos].minInter=min(lazy[pos].minInter,valModif);
lazy[pos].maxInter=min(lazy[pos].maxInter,valModif);
}
pushFlag(pos);
}
else {
pushFlag(pos);
if (lazy[pos].debInter!=lazy[pos].finInter) {
modif(2*pos,deb,fin,typeModif,valModif);
modif(2*pos+1,deb,fin,typeModif,valModif);
}
}
}
int calcVal(int pos,int posVal) {
pushFlag(pos);
if (lazy[pos].debInter<=posVal and lazy[pos].finInter>=posVal) {
if (lazy[pos].debInter!=lazy[pos].finInter) {
return calcVal(2*pos,posVal)+calcVal(2*pos+1,posVal);
}
else {
return lazy[pos].minInter;
}
}
else {
return 0;
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
nbVal=n;
nbReq=k;
init(1,0,nbVal-1);
for (int i=0;i<nbReq;i++) {
modif(1,left[i],right[i],op[i],height[i]);
/*for (int j=0;j<nbVal;j++) {
cout<<calcVal(1,j)<<" ";
}
cout<<endl;*/
}
for (int i=0;i<nbVal;i++) {
finalHeight[i]=calcVal(1,i);
}
return;
}
