#include "wall.h"
#include <bits/stdc++.h>
// Ghulam Junaid 's Solution
using namespace std;
const int N = 2e6 + 10;
int n, q;
struct node{
int mx, mn, lazy = -1;
} seg[4 * N];
void push(int v){
if (seg[v].lazy == -1) return;
int lc = 2 * v, rc = lc + 1;
seg[lc].mn = seg[v].lazy, seg[rc].mn = seg[v].lazy;
seg[lc].mx = seg[v].lazy, seg[rc].mx = seg[v].lazy;
seg[lc].lazy = seg[v].lazy, seg[rc].lazy = seg[v].lazy;
seg[v].lazy = -1;
}
void adding(int l, int r, int val, int v = 1, int s = 0, int e = n){
if (r <= s || e <= l) return;
if (l <= s && e <= r){
if (seg[v].mx <= val){
seg[v].mx = val;
seg[v].mn = val;
seg[v].lazy = val;
return;
}
if (seg[v].mn >= val)
return;
}
push(v);
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
adding(l, r, val, lc, s, mid);
adding(l, r, val, rc, mid, e);
seg[v].mx = max(seg[lc].mx, seg[rc].mx);
seg[v].mn = min(seg[lc].mn, seg[rc].mn);
}
void removing(int l, int r, int val, int v = 1, int s = 0, int e = n){
if (r <= s || e <= l) return;
if (l <= s && e <= r){
if (seg[v].mx <= val)
return;
if (seg[v].mn >= val){
seg[v].mx = val;
seg[v].mn = val;
seg[v].lazy = val;
return;
}
}
push(v);
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
removing(l, r, val, lc, s, mid);
removing(l, r, val, rc, mid, e);
seg[v].mx = max(seg[lc].mx, seg[rc].mx);
seg[v].mn = min(seg[lc].mn, seg[rc].mn);
}
int get(int p, int v = 1, int s = 0, int e = n){
if (e - s == 1) return seg[v].mn;
push(v);
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
if (p < mid) return get(p, lc, s, mid);
return get(p, rc, mid, e);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N, q = k;
for (int i=0; i<q; i++){
if (op[i] == 1)
adding(left[i], right[i] + 1, height[i]);
else
removing(left[i], right[i] + 1, height[i]);
}
for (int i=0; i<n; i++)
finalHeight[i] = get(i);
for (int i=0; i<n; i++)
if (finalHeight[i] == -1) finalHeight[i] = 0;
}
