#include "wall.h"
#include <algorithm>
#include <set>
#include <vector>

#define PB push_back

using namespace std;

const int N = 1e5 + 10;
const int OO = 0x7FFFFFFF;

vector<int> up[N][2][2];
multiset<int> lw, hg;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int f[]){
	for(int i = 0; i < k; ++i) { 
		up[left[i]][op[i] - 1][0].PB(height[i]);
		up[right[i]][op[i] - 1][1].PB(height[i]);
	}

	for(int i = 0; i < n; ++i) { 
		for(int x : up[i][0][0]) { 
			hg.insert(x);
		}
		for(int x : up[i][1][0]) { 
			lw.insert(x);
		}

		int mx = hg.empty() ? 0 : *prev(hg.end());
		int mn = lw.empty() ? OO : *(lw.begin());

		f[i] = max(f[i], mx);
		f[i] = min(f[i], mn);

		for(int x : up[i][0][1]) { 
			hg.erase(hg.find(x));
		}
		for(int x : up[i][1][1]) { 
			lw.erase(lw.find(x));
		}
	}
	return;
}