#include "wall.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
static const int N = 1<<21;
static int mn[N<<1];
static int mx[N<<1];
static inline void ppg(int i)
{
if (mn[i] == mx[i]) {
mn[2*i+1] = mx[2*i+1] = mn[i];
mn[2*i+2] = mx[2*i+2] = mn[i];
}
}
static inline void up(int i)
{
mn[i] = min(mn[2*i+1], mn[2*i+2]);
mx[i] = max(mx[2*i+1], mx[2*i+2]);
}
static void inc(int l, int r, int h, int i=0, int b=0, int e=N)
{
if (l <= b && e <= r && mx[i] <= h) {
mn[i] = mx[i] = h;
return;
}
if (r <= b || e <= l || mn[i] >= h)
return;
ppg(i);
inc(l, r, h, 2*i+1, b, (b+e)/2);
inc(l, r, h, 2*i+2, (b+e)/2, e);
up(i);
}
static void dec(int l, int r, int h, int i=0, int b=0, int e=N)
{
if (l <= b && e <= r && mn[i] >= h) {
mn[i] = mx[i] = h;
return;
}
if (r <= b || e <= l || mx[i] <= h)
return;
ppg(i);
dec(l, r, h, 2*i+1, b, (b+e)/2);
dec(l, r, h, 2*i+2, (b+e)/2, e);
up(i);
}
static int get(int p, int i=0, int b=0, int e=N)
{
if (mn[i] == mx[i])
return mn[i];
if (p < (b+e)/2)
return get(p, 2*i+1, b, (b+e)/2);
else
return get(p, 2*i+2, (b+e)/2, e);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
Loop (i,0,k) {
if (op[i] == 1)
inc(left[i], right[i]+1, height[i]);
else
dec(left[i], right[i]+1, height[i]);
}
Loop (i,0,n)
finalHeight[i] = get(i);
}
