This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int64_t MXN = 2e6;
vector<int64_t>uptree(4*MXN);
vector<int64_t>downtree(4*MXN);
int64_t func(int64_t a,int64_t b){
return min(a,b);
}
void build(int64_t node,int64_t node_low,int64_t node_high){
if (node_low==node_high){
uptree[node]=0;
downtree[node]=INT_MAX;
}
else {
int64_t mid =(node_low+node_high)>>1;
build(node*2,node_low,mid);
build(node*2 + 1,mid+1,node_high);
uptree[node]=func(uptree[node*2],uptree[node*2 + 1]);
downtree[node]=func(downtree[node*2],downtree[node*2 + 1]);
}
}
void push(int64_t x){
uptree[x + x] = max(uptree[x],uptree[x+x]);
uptree[x + x + 1] = max(uptree[x],uptree[x+x + 1]);
downtree[x + x] = min(downtree[x],downtree[x+x]);
downtree[x + x + 1] = min(downtree[x],downtree[x+x+1]);
uptree[x+x] = min(uptree[x+x],downtree[x]);
uptree[x+x+1] = min(uptree[x+x+1],downtree[x]);
downtree[x + x] = max(uptree[x],downtree[x+x]);
downtree[x + x + 1] = max(uptree[x],downtree[x+x+1]);
}
void update(int64_t node,int64_t node_low,int64_t node_high,int64_t q_low,int64_t q_high,int64_t new_val,int ok){
if (node_low>node_high||node_low>q_high||node_high<q_low)return;
if (q_low<=node_low&&q_high>=node_high){
if (ok==1){
uptree[node] = max(uptree[node],new_val);
downtree[node] = max(downtree[node],new_val);
}
else{
uptree[node] = min(uptree[node],new_val);
downtree[node] = min(downtree[node],new_val);
}
return ;
}
push(node);
downtree[node]=INT_MAX, uptree[node]=0;
int64_t mid = (node_low + node_high)/2;
update(node*2,node_low,mid,q_low,q_high,new_val,ok);
update(node*2 + 1,mid + 1,node_high,q_low,q_high,new_val,ok);
downtree[node]= func(downtree[node*2],downtree[node*2 + 1]);
uptree[node]= func(uptree[node*2],uptree[node*2 + 1]);
}
int64_t query(int64_t node,int64_t node_low,int64_t node_high,int64_t query_low,int64_t query_high){
if (node_low>node_high||node_low>query_high||node_high<query_low)return INT_MAX;
if (query_low<=node_low&&query_high>=node_high){
return min(uptree[node],downtree[node]);
}
push(node);
int64_t mid = (node_low+node_high)/2;
return func(query(node*2,node_low,mid,query_low,query_high),query(node*2 + 1,mid+1,node_high,query_low,query_high));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1,0,n-1);
for (int i =0;i<k;++i){
update(1,0,n-1,left[i],right[i],height[i],op[i]);
}
for (int i = 0;i<n;++i){
finalHeight[i] = query(1,0,n-1,i,i);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |