| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 596110 | neki | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define vc vector
using namespace std;
const int mn=2000000;
int tl[4 * mn], tr[4 * mn];
void apply(int no, int m, int M){
if(tr[no]<=m) tl[no]=tr[no]=m;
else if(M<=tl[no]) tl[no]=tr[no]=M;
else tl[no]=max(tl[no], m), tr[no]=min(tr[no], M);
}
void push(int no){
apply(no * 2 +1, tl[no], tr[no]);
apply(no * 2 +2, tl[no], tr[no]);
tl[no]=0, tr[no]=INT_MAX;
}
void update(int ql, int qr, int m, int M, int l, int r, int no){
if(ql==l and qr==r) apply(no, m, M);
else{
int mid=(l+r)/2;
push(no);
if(qr<=mid) update(ql, qr, m, M, l, mid, no * 2 +1);
else if(mid<ql) update(ql, qr, m, M, mid+1, r, no * 2 +2);
else update(ql, mid, m, M, l, mid, no * 2 + 1), update(mid+1, qr, m, M, mid+1, r, no * 2 +2);
}
}
void build(int l, int r, int no, vc<int>& ans){
if(l==r) ans[l]=tl[no];
else{
int mid=(l+r)/2;
push(no);
build(l, mid, no * 2 +1, ans);
build(mid+1, r, no * 2 + 2, ans);
}
}
void buildWall(int n, int k, vc<int> op, vc<int> ql, vc<int> qr, vc<int> h, vc<int>& ans){
for(int i=0;i<k;++i){
if(op[i]==1) update(ql[i], qr[i], h[i], INT_MAX, 0, n-1, 0);
if(op[i]==2) update(ql[i], qr[i], 0, h[i], 0, n-1, 0);
}
build(0, n-1, 0, ans);
}