#include "bits/stdc++.h" #include "wall.h" // #include "grader.cpp" using namespace std; #define N 500005 int D[N], U[N], finalH[N]; void combine(int l,int r,int ind) { if(l == r) return; D[ind * 2] = min(D[ind * 2], D[ind]); D[ind * 2] = max(D[ind * 2], U[ind]); U[ind * 2] = min(U[ind * 2], D[ind]); U[ind * 2] = max(U[ind * 2], U[ind]); D[ind * 2 + 1] = min(D[ind * 2 + 1], D[ind]); D[ind * 2 + 1] = max(D[ind * 2 + 1], U[ind]); U[ind * 2 + 1] = min(U[ind * 2 + 1], D[ind]); U[ind * 2 + 1] = max(U[ind * 2 + 1], U[ind]); U[ind] = INT_MIN; D[ind] = INT_MAX; return; } void upd(int l,int r,int ind,int tp, int x,int y,int vl) { if(r < x || l > y) return; combine(l, r, ind); if(l >= x && r <= y) { if(tp == 1){ U[ind] = max(U[ind], vl); D[ind] = max(D[ind], vl); } else { U[ind] = min(U[ind], vl); D[ind] = min(D[ind], vl); } return; } int mid = (l + r) / 2; upd(l, mid, ind * 2, tp, x, y, vl); upd(mid + 1, r, ind * 2 + 1, tp, x, y, vl); } void build(int l,int r,int ind) { if(l == r) { // cout << l << " " << U[ind] << " " << D[ind] << '\n'; finalH[l] = min(U[ind], D[ind]); return; } combine(l, r, ind); int mid = (l + r) / 2; build(l,mid,ind*2); build(mid+1,r,ind*2+1); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ for(int i = 0; i < k; i++) { upd(1, n, 1, op[i], left[i] + 1, right[i] + 1, height[i]); } build(1, n, 1); for(int i = 0; i < n; i++) { finalHeight[i] = finalH[i + 1]; } return; }