# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
480141 | Apiram | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int64_t MXN = 1e6;
vector<int64_t>tree(4*MXN);
vector<int64_t>lazy(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){
tree[node]=0;
}
else {
int64_t mid =(node_low+node_high)>>1;
build(node*2,node_low,mid);
build(node*2 + 1,mid+1,node_high);
tree[node]=func(tree[node*2],tree[node*2 + 1]);
}
}
void push(int64_t x){
tree[x + x] = min(tree[x],tree[x+x]);
tree[x + x + 1] = min(tree[x],tree[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){
tree[node] = max(tree[node],new_val);
}
else{
tree[node] = min(tree[node],new_val);
}
return ;
}
push(node);
int64_t mid = (node_low + node_high)/2;
update(node*2,node_low,mid,q_low,q_high,new_val);
update(node*2 + 1,mid + 1,node_high,q_low,q_high,new_val);
tree[node]= func(tree[node*2],tree[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 0;
if (query_low<=node_low&&query_high>=node_high){
return tree[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);
}
}