#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
ll N, K, blocksz;
vector<ll>ans, ans2;
vector<ll>values;
ll block[1500][2]; // minimo, maximo
void updateThis(ll blc){
for(int i = blc*blocksz ; i < (blc+1)*blocksz ; i++){
if(values[i]<=block[blc][0])values[i] = block[blc][0];
if(values[i]>=block[blc][1])values[i] = block[blc][1];
//cout << i << " = " << values[i] << endl;
}
block[blc][0]=0;
block[blc][1]=1000000000;
}
void push(ll l, ll r, ll op, ll curr){
int currentBlock = l/blocksz, lastblock = r/blocksz;
updateThis(currentBlock);
for(int i = l ; i < min((currentBlock+1)*blocksz, r+1) ; i++){
if(op==1)values[i] = max(values[i], curr);
else values[i] = min(values[i], curr);
}
for(int i = currentBlock+1 ; i < lastblock ; i++){
if(op==1){
if(block[i][0]<curr){
//cout<< " block" << i << " min " << curr << endl;
block[i][0]=curr;
block[i][1]=max(curr, block[i][1]);
}
}else{
if(block[i][1]>curr){
//cout<< " block" << i << " max " << curr << endl;
block[i][1]=curr;
block[i][0]=min(block[i][0], curr);
}
}
}
if(currentBlock == lastblock)return ;
updateThis(lastblock);
for(int i = lastblock*blocksz ; i <= r ; i++){
if(op==1)values[i] = max(values[i], curr);
else values[i] = min(values[i], curr);
//cout<<"ed " << i << " ";
}
//cout << endl;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N=n, K=k;
for(int i = 0 ; i < n ; i ++){
values.pb(0);
}
blocksz = sqrt(n);
for(int i = 0 ; i < blocksz+1 ; i++){
block[i][0]=0;
block[i][1]=1000000000;
}
for(int i = 0 ; i < k ; i++){
push(left[i], right[i], op[i], height[i]);
}
for(int i = 0 ; i < blocksz +1 ; i++){
updateThis(i);
}
for(int i = 0 ; i < n ; i ++)finalHeight[i] = values[i];
return;
}
