이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#include "wall.h"
using namespace std;
using ll = long long;
const int maxn=2e6+5;
const int N = 5e5+5;
int T[4 * maxn][2];
void build(int l,int r,int nd){
T[nd][1] = 1e5;
if(l == r) return;
int md = (l + r) >> 1;
build(l,md,nd<<1);
build(md+1,r,nd<<1 | 1);
}
void prop(int nd){
if(T[nd][0] == -1) return;
int cep = (nd << 1);
int sag = (nd << 1 | 1);
if(T[cep][0] == -1){
T[cep][0] = T[nd][0];
T[cep][1] = T[nd][1];
}
else if(T[cep][0] > T[nd][1]){
T[cep][0] = T[nd][1];
T[cep][1] = T[nd][1];
}
else if(T[cep][1] < T[nd][0]){
T[cep][0] = T[nd][0];
T[cep][1] = T[nd][0];
}
else {
T[cep][0] = max(T[cep][0],T[nd][0]);
T[cep][1] = min(T[cep][1],T[nd][1]);
}
if(T[sag][0] == -1){
T[sag][0] = T[nd][0];
T[sag][1] = T[nd][1];
}
else if(T[sag][0] > T[nd][1]){
T[sag][0] = T[nd][1];
T[sag][1] = T[nd][1];
}
else if(T[sag][1] < T[nd][0]){
T[sag][0] = T[nd][0];
T[sag][1] = T[nd][0];
}
else {
T[sag][0] = max(T[sag][0],T[nd][0]);
T[sag][1] = min(T[sag][1],T[nd][1]);
}
T[nd][0] = -1;
T[nd][1] = -1;
}
void upd(int a,int b,int lft,int rgt,int l,int r,int nd){
if(r < a or l > b) return;
if(l >= a and r <= b){
if(T[nd][0] == -1){
T[nd][0] = lft;
T[nd][1] = rgt;
return;
}
if(rgt < T[nd][0]){
T[nd][0] = rgt;
T[nd][1] = rgt;
}
else if(lft > T[nd][1]){
T[nd][0] = lft;
T[nd][1] = rgt;
}
else {
T[nd][0] = max(T[nd][0],lft);
T[nd][1] = min(T[nd][1],rgt);
}
return;
}
prop(nd);
int md = (l + r) >> 1;
upd(a,b,lft,rgt,l,md,nd<<1);
upd(a,b,lft,rgt,md+1,r,nd<<1 | 1);
}
int jog[maxn];
void f(int l,int r,int nd){
if(l == r){
jog[l] = T[nd][0];
return;
}
prop(nd);
int md = (l + r) >> 1;
f(l,md,nd<<1);
f(md+1,r,nd<<1 | 1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(0,n-1,1);
for(int i = 0;i < k;i++){
// cout<<left[i]<<' '<<right[i]<<' '<<height[i]<<'\n';
if(op[i] == 2) upd(left[i],right[i],0,height[i],0,n-1,1);
else upd(left[i],right[i],height[i],1e5,0,n-1,1);
}
f(0,n-1,1);
for(int i = 0;i < n;i++){
finalHeight[i] = jog[i];
// cout<<jog[i]<<' ';
}
return;
}
// int n,k;
// int op[N],l[N],r[N],h[N],ans[maxn];
// int main(){
// cin >> n >> k;
// for(int i = 0;i < k;i++) cin >> op[i] >> l[i] >> r[i] >> h[i];
// buildWall(n,k,op,l,r,h,ans);
// for(int i = 0;i < n;i++) cout<<ans[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... |