#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
#ifdef __LOCAL__
#include "grader.cpp"
#endif // __LOCAL__
#include "wall.h"
const int INF = 1e9;
const int MAXN = 2e6 + 5;
class SegmentTree
{
private:
struct Node
{
int Min, Max;
Node()
{
Min = INF;
Max = -INF;
}
Node(int Min, int Max)
:Min(Min), Max(Max){}
bool operator== (const Node &other)
{
return (this->Min == other.Min)&&(this->Max == other.Max);
}
};
int N;
Node lazy[4*MAXN];
void UpdateLazy(int type, int value, int node)
{
if (type == 1) // Max
{
lazy[node].Min = max(lazy[node].Min, value);
lazy[node].Max = max(lazy[node].Max, value);
}
if (type == 2) // Min
{
lazy[node].Min = min(lazy[node].Min, value);
lazy[node].Max = min(lazy[node].Max, value);
}
}
void PushdownLazy(int node)
{
UpdateLazy(1, lazy[node].Max, 2*node);
UpdateLazy(2, lazy[node].Min, 2*node);
UpdateLazy(1, lazy[node].Max, 2*node+1);
UpdateLazy(2, lazy[node].Min, 2*node+1);
lazy[node] = Node();
}
void UpdateInternal(int type, int queryL, int queryR, int value, int node, int l, int r)
{
if (l > queryR || r < queryL)
return;
if (queryL <= l && r <= queryR)
{
UpdateLazy(type, value, node);
return;
}
PushdownLazy(node);
UpdateInternal(type, queryL, queryR, value, 2*node, l, (l+r)/2);
UpdateInternal(type, queryL, queryR, value, 2*node+1, (l+r)/2+1, r);
}
void AnswerInternal(int finalHeight[], int node, int l, int r)
{
if (l == r)
{
if (lazy[node].Min > lazy[node].Max)
swap(lazy[node].Min, lazy[node].Max);
if (abs(lazy[node].Min) == INF)
{
finalHeight[l] = 0;
}
else
{
finalHeight[l] = lazy[node].Min;
}
return;
}
PushdownLazy(node);
AnswerInternal(finalHeight, 2*node, l, (l+r)/2);
AnswerInternal(finalHeight, 2*node+1, (l+r)/2+1, r);
}
public:
SegmentTree(){}
SegmentTree(int n)
{
N = n;
}
void Update(int type, int queryL, int queryR, int value)
{
UpdateInternal(type, queryL, queryR, value, 1, 0, N-1);
}
void Answer(int finalHeight[])
{
AnswerInternal(finalHeight, 1, 0, N-1);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
SegmentTree *tree = new SegmentTree(n);
for (int i = 0; i < n; i++)
{
tree->Update(op[i], left[i], right[i], height[i]);
}
tree->Answer(finalHeight);
return;
}
