#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
//segment tree, rmaxq
struct Node{
int s,e,m,v=0;
Node *l, *r;
Node(int _s, int _e){
s=_s;e=_e;
if (s==e){
return;
}
m=(s+e)/2;
l = new Node(s,m);
r = new Node(m+1,e);
}
void update(int ind, int val){
//cout<<"upd "<<ind<<" "<<val<<'\n';
if (s==e){
v=val;
return;
}
if (ind<=m){
l->update(ind,val);
} else {
r->update(ind,val);
}
v=max(l->v,r->v);
}
int query(int a, int b){
if (s==a&&e==b){
return v;
}
if (b<=m){
return l->query(a,b);
} else if (m<a){
return r->query(a,b);
} else {
return max(l->query(a,m),r->query(m+1,b));
}
}
};
Node *radd;
Node *rrem;
int MX = 100001;
int n,k;
bool success(int x){
if (x==k){return true;}
return (radd->query(x,k-1)+rrem->query(x,k-1))<=MX;
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
n=N;k=K;
vector<pair<int,pair<int,bool>>> ptrs[2000000];
int kadd[500000];
//{time,{height,add/rem}}
for (int i = 0; i<k; i++){
bool phase = (op[i]-1);
int h = height[i];
int l = left[i];
int r = right[i];
if (phase){
h=MX-h;
}
ptrs[l].push_back({i,{h,phase}});
if (r!=n-1){
ptrs[r+1].push_back({i,{0,phase}});
}
kadd[i]=0;
}
radd=new Node(0,k-1);
rrem=new Node(0,k-1);
int prevval = 0;
for (int x = 0; x<n; x++){
//cout<<x<<":\n";
//process x
if (ptrs[x].size()==0){
finalHeight[x]=prevval;
//cout<<prevval<<'\n';
continue;
}
for (auto i : ptrs[x]){
int time = i.first;
int h = i.second.first;
int isRem = i.second.second;
if (isRem){
rrem->update(time,h);
} else {
radd->update(time,h);
kadd[time]=h;
}
}
int l = 0, r = k-1;
while (l<=r){
int mid = (l+r)/2;
//cout<<mid<<'\n';
if (success(mid)){
r=mid-1;
} else {
l=mid+1;
}
}
//cout<<"bleh\n";
if (l==0){
//there is no overlap
finalHeight[x] = radd->query(0,k-1);
} else {
//there is overlap
int lastind = l-1;
int addafter = radd->query(lastind,k-1);
int remafter = rrem->query(lastind,k-1);
int addval = kadd[lastind];
if (addval+remafter>MX){
//remove is after
finalHeight[x]=MX-remafter;
} else {
//add is after
finalHeight[x]=addafter;
}
}
prevval=finalHeight[x];
//cout<<prevval<<'\n';
}
}
