#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF 1e6
#define zero (int)0
#define MX (int)3e5+5
#define LMX (int)1e7
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
const int mod = 1e9+7; //may fixer to that 99.. number.
struct fixer
{
int down, up;
};
fixer crate(const int &a, const int &b)
{
fixer ok;
ok.down = a;
ok.up = b;
assert(a<=b);
return ok;
}
fixer identity = crate(-INF, INF);
fixer superimpose(const fixer &c1, const fixer &c2)
{
fixer c3;
c3.down = max(c1.down, c2.down);
c3.up = min(c1.up, c2.up);
if(c3.up >= c3.down)
return c3;
if(c3.down == c2.down)
return crate(c1.up, c1.up);
else
return crate(c1.down, c1.down);
}
struct segment_tree
{
vector<int> tree;
vector<fixer> lazy;
void init()
{
tree.assign(LMX, 0);
lazy.assign(LMX, identity);
return;
}
void apply(int id, fixer c)
{
if(tree[id] <= c.down)
tree[id] = c.down;
if(tree[id] >= c.up)
tree[id] = c.up;
lazy[id] = superimpose(c, lazy[id]);
return;
}
void push(int id)
{
apply(2*id, lazy[id]);
apply(2*id+1, lazy[id]);
lazy[id] = identity;
return;
}
void upd(fixer place, int ql, int qr, int id, int l, int r)
{
if(qr < l || r < ql)
return;
if(ql <= l && r <= qr)
{
apply(id, place);
return;
}
int m = (l+r)/2;
push(id);
upd(place, ql, qr, 2*id, l, m);
upd(place, ql, qr, 2*id+1, m+1, r);
return;
}
int val(int pos, int id, int l, int r)
{
int m = (l+r)/2;
if(l==r)
return tree[id];
push(id);
if(pos <= m)
return val(pos, 2*id, l, m);
else
return val(pos, 2*id+1, m+1, r);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
segment_tree work;
work.init();
for(int i = 0; i < k; i++)
{
if(op[i] == 1)
work.upd(crate(height[i], INF), left[i], right[i], 1, 0, n-1);
else
work.upd(crate(-INF, height[i]), left[i], right[i], 1, 0, n-1);
}
for(int i = 0; i < n; i++)
finalHeight[i] = work.val(i, 1, 0, n-1);
return;
}
