#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
///////
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
int INF=2000000000;
struct node{
int l;
int r;
int left;
int right;
pii minmax;
};
pii combine(pii a, pii b){ // a antes que b
pii res;
res.first=max(a.first,b.first);
res.second=min(a.second,b.second);
if (res.first>res.second){
if(a.first<b.first) res.second=res.first;
else res.first=res.second;
}
//cerr << a.first << ' '<<a.second << ' '<<b.first<<' '<<b.second<<' '<<res.first<<' '<<res.second<<'\n';
return res;
}
int counter=0;
vector<node> st(5000000);
void create_tree(int l, int r){
int ac=counter;
st[ac].l=l;
st[ac].r=r;
st[ac].minmax=pii{0,0};
if (l!=r){
//st[ac].minmax=pii{0,INF};
counter++;
st[ac].left=counter;
create_tree(l,(l+r)/2);
counter++;
st[ac].right=counter;
create_tree((l+r)/2+1,r);
}
}
void push_tree(int ac, int l, int r, pii x){
if (l==st[ac].l and r==st[ac].r){
st[ac].minmax=combine(st[ac].minmax,x);
return;
}
else{
push_tree( st[ac].left , st[ac].l , (st[ac].l+st[ac].r)/2 , st[ac].minmax );
push_tree( st[ac].right , (st[ac].l+st[ac].r)/2+1 , st[ac].r , st[ac].minmax );
st[ac].minmax=pii{0,INF};
int med=(st[ac].l+st[ac].r)/2;
if (l>med){
push_tree(st[ac].right , l , r , x);
}
else if (r<=med){
push_tree(st[ac].left , l , r , x);
}
else{
push_tree( st[ac].left , l , med , x );
push_tree( st[ac].right, med+1 , r , x);
}
return;
}
}
void buildWall(int n, int k, int type[], int left[], int right[], int height[], int finalHeight[]){
create_tree(0,n-1);
for (int i=0;i<k;i++){
if (type[i]==1){
push_tree(0,left[i],right[i],pii{height[i],INF});
}
else{
push_tree(0,left[i],right[i],pii{0,height[i]});
}
//for (int x=0;x<n;x++){
// push_tree(0,x,x,pii{0,INF});
//}
//int x=0;
//int j=0;
//while (x<n){
// if (st[j].l==st[j].r){
// //cerr << st[j].l << ' '<<st[j].minmax.first<<'\n';
// x++;
// }
// j++;
//}
}
for (int x=0;x<n;x++){
push_tree(0,x,x,pii{0,INF});
}
int i=0;
int j=0;
while (i<n){
if (st[j].l==st[j].r){
finalHeight[st[j].l]=st[j].minmax.first;
i++;
}
j++;
}
return;
}
