#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int MAX_N = 2000000;
const int NINF = 0;
const int INF = (1<<30);
struct node {
int opmin = INF;
int opmax = NINF;
};
node segt[4*MAX_N+1];
void app(int idx, node a){
segt[idx].opmax = min(max(segt[idx].opmax,a.opmax), a.opmin);
segt[idx].opmin = min(max(segt[idx].opmin,a.opmax),a.opmin);
return;
}
void upd(int l, int r, int idx, int tl, int tr, int w, int h){
if (l > tr || r < tl){
return;
}
if (l >= tl && r <= tr){
//mini
if (w == 1){
segt[idx].opmin = min(segt[idx].opmin,h);
segt[idx].opmax = min(segt[idx].opmax,h);
} else {
segt[idx].opmin = max(segt[idx].opmin,h);
segt[idx].opmax = max(segt[idx].opmax,h);
}
return;
}
int m = (l+r)/2;
app(2*idx+1,segt[idx]);
app(2*idx+2,segt[idx]);
segt[idx].opmin = INF;
segt[idx].opmax = NINF;
upd(l,m,2*idx+1,tl,tr,w,h);
upd(m+1,r,2*idx+2,tl,tr,w,h);
return;
}
void solve(int l, int r, int idx, int finalHeight[]){
if (l == r){
//cout << l << ": " << segt[idx].opmin << ", " << segt[idx].opmax << '\n';
if (segt[idx].opmin == INF && segt[idx].opmax == NINF){
finalHeight[l] = 0;
} else {
finalHeight[l] = min(segt[idx].opmin,segt[idx].opmax);
}
return;
}
int m = (l+r)/2;
app(2*idx+1,segt[idx]);
app(2*idx+2,segt[idx]);
segt[idx].opmin = INF;
segt[idx].opmax = NINF;
solve(l,m,2*idx+1,finalHeight);
solve(m+1,r,2*idx+2,finalHeight);
return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i =0; i < k; i++){
upd(0,n-1,0,left[i],right[i],op[i]-1,height[i]);
}
solve(0,n-1,0,finalHeight);
return;
}
Compilation message
Compilation timeout while compiling wall
