#include "wall.h"
//#include "grader.cpp"
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 2e6 + 5;
struct Range
{
int l, r;
Range(){}
Range(int l, int r)
{
this->l = l;
this->r = r;
}
int f(int x)
{
if(x<=l) return l;
if(x>=r) return r;
return x;
}
};
Range Merge(Range first, Range second)
{
if(second.l>=first.r) return Range(second.l, second.l);
if(second.r<=first.l) return Range(second.r, second.r);
if(second.l<=first.l && first.r<=second.r) return Range(first.l, first.r);
if(first.l<=second.l && second.r<=first.r) return Range(second.l, second.r);
if(first.l<=second.l && first.r<=second.r && second.l<=first.r) return Range(second.l, first.r);
if(second.l<=first.l && second.r<=first.r && first.l<=second.r) return Range(first.l, second.r);
}
struct SegmentTree
{
Range val;
int l, r;
SegmentTree *L, *R;
SegmentTree(){}
SegmentTree(int l, int r)
{
this->val = Range(0, MAXN);
this->l = l;
this->r = r;
this->L = nullptr;
this->R = nullptr;
}
void build()
{
if(l==r) return;
L = new SegmentTree(l, (l+r)/2);
R = new SegmentTree((l+r)/2+1, r);
L->build();
R->build();
}
void rem(int q)
{
if(l==r && q==l)
{
val = Range(0, MAXN);
return;
}
if(q<l || q>r) return;
L->rem(q);
R->rem(q);
val = Merge(L->val, R->val);
}
void add(int q, Range newVal)
{
if(l==r && q==l)
{
val = newVal;
return;
}
if(q<l || q>r) return;
L->add(q, newVal);
R->add(q, newVal);
val = Merge(L->val, R->val);
}
void reset()
{
//if(val==Range(0, MAXN)) return;
val = Range(0, MAXN);
if(L!=nullptr)
{
L->reset();
R->reset();
}
}
};
vector <int> toRemove[MAXN], toAdd[MAXN];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
SegmentTree *T = new SegmentTree(0, k-1);
T->build();
for(int i = 0;i<k;i++)
{
toAdd[ left[i] ].push_back(i);
toRemove[ right[i] ].push_back(i);
}
for(int ind = 0;ind<n;ind++)
{
if(ind!=0)
{
for(int i: toRemove[ind-1])
T->rem(i);
}
for(int i: toAdd[ind])
{
if(op[i]==1) T->add(i, Range(height[i], MAXN));//ans = Merge(ans, Range(height[i], MAXN));
else T->add(i, Range(0, height[i]));//ans = Merge(ans, Range(0, height[i]));
}
finalHeight[ind] = T->val.f(0);
}
}
