| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1147985 | Saul0906 | 벽 (IOI14_wall) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "wall.h"
#define mid ((l+r)>>1)
#define fi first
#define se second
#define pii pair<int, int>
#define rep(a,b,c) for(int a=b; a<c; a++)
using namespace std;
using vi = vector<int>;
const int inf=1e9+5;
struct segtree{
segtree *left, *right;
int l, r;
vi a;
pii upd={0,0};
segtree(int x, int y): l(x), r(y){
if(l==r) return;
left = new segtree(l,mid);
right = new segtree(mid+1,r);
}
void prop(){
if(!upd.fi) return;
if(l<r){
left->upd = upd;
right->upd = upd;
}
upd={0,0};
}
void update(int x, int y, int h, int z){
prop();
if(y<l || r<x) return;
if(x<=l && r<=y){
upd={z,h};
return;
}
left->update(x,y,h,z);
right->update(x,y,h,z);
}
pii query(int x){
if(x<l || r<x) return {0,-5};
if(x<=l && r<=x) return upd;
pii A, B;
A=left->query(x);
B=right->query(x);
if(upd.fi==1 && A.se>=0) return {upd.fi,max(A.se,upd.se)};
else if(upd.fi==1 && B.se>=0) return {upd.fi,max(B.se,upd.se)};
else if(upd.fi==2 && A.se>=0) return {upd.fi, min(A.se,upd.se)};
else if(upd.fi==2 && B.se>=0) return {upd.fi, min(B.se,upd.se)};
return {0,0};
}
};
void buildWall(int n, int k, vi op, vi left, vi right, vi height, vi finalHeight){
segtree st(0,n-1);
rep(i,0,k) st.update(left[i],right[i],height[i],op[i]);
rep(i,0,n) finalHeight[i]=st.query(i).se;
return;
}