#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 2000010
#define ll long long
#define maxk 500010
const ll inf = 12345678901234567LL;
ll seg[maxn*4];
ll cmin[maxn*4], cmax[maxn*4];
int N, K;
//maintain cmax[si] <= cmin[si]
void delaze(int ss, int se, int si) {
seg[si] = max(seg[si], cmax[si]);
seg[si] = min(seg[si], cmin[si]);
if (ss != se) {
ll nmin = cmin[si];
ll nmax = cmax[si];
for (int d = 1; d <= 2; d++) {
int pos = 2*si+d;
if (nmin <= cmax[pos]) {
cmax[pos] = nmin;
cmin[pos] = nmin;
continue;
}
if (nmax >= cmin[pos]) {
cmin[pos] = nmax;
cmax[pos] = nmax;
continue;
}
if (nmin <= cmin[pos]) { //new thing is more effective, order should not matter here
cmin[pos] = nmin;
}
if (nmax >= cmax[pos]) { //new thing is more effective, preliminary operations affect nothing
cmax[pos] = nmax;
}
}
}
cmin[si] = inf; //reset the values
cmax[si] = -1;
}
void up(int us, int ue, ll nmin, ll nmax, int ss, int se, int si) {
delaze(ss, se, si);
if (us > ue || ss > se || us > se || ue < ss) return;
if (us <= ss && se <= ue) {
cmin[si] = nmin; //direct assign b/c we know it is delazed
cmax[si] = nmax;
delaze(ss, se, si);
return;
}
int mid = (ss+se)/2;
up(us, ue, nmin, nmax, ss, mid, si*2+1);
up(us, ue, nmin, nmax, mid+1, se, si*2+2);
}
void update(int us, int ue, ll nmin, ll nmax) {
up(us, ue, nmin, nmax, 0, N-1, 0);
}
int qu(int spot, int ss, int se, int si) {
delaze(ss, se, si);
if (ss == se) return seg[si];
int mid = (ss+se)/2;
if (spot <= mid) return qu(spot, ss, mid, si*2+1);
return qu(spot, mid+1, se, si*2+2);
}
int query(int spot) {
return qu(spot, 0, N-1, 0);
}
void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]){
fill(seg, seg+maxn*4, 0);
fill(cmax, cmax+maxn*4, -1);
fill(cmin, cmin+maxn*4, inf);
N = n;
K = k;
//do the queries
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
//max operation
update(left[i], right[i], inf, height[i]);
}
else {
//min operation
update(left[i], right[i], height[i], -1);
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = query(i);
}
return;
}
