| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 20886 | 14kg | 벽 (IOI14_wall) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#define N 2000001
#define max2(x,y) (x>y?x:y)
#define min2(x,y) (x<y?x:y)
struct WALL{
int op, h;
} Tree[N * 4][2], NONO;
int n, nn, m;
WALL make_WALL(int op, int h){
WALL temp;
temp.op = op, temp.h = h;
return temp;
}
void g(int lev, WALL num){
if (num.op == -1) return;
if (Tree[lev][0].op == -1){ Tree[lev][0] = num; return; }
if (Tree[lev][1].op == -1){ Tree[lev][1] = num; return; }
if (Tree[lev][0].op == Tree[lev][1].op){
if (Tree[lev][0].op == 1) Tree[lev][0].h = max2(Tree[lev][0].h, Tree[lev][1].h);
else Tree[lev][0].h = min2(Tree[lev][0].h, Tree[lev][1].h);
Tree[lev][1] = num; return;
}
if (Tree[lev][1].op == num.op){
if (num.op == 1) Tree[lev][1].h = max2(Tree[lev][1].h, num.h);
else Tree[lev][1].h = min2(Tree[lev][1].h, num.h);
return;
}
if (Tree[lev][1].op == 1){
if (Tree[lev][1].h > Tree[lev][0].h){
if (num.h < Tree[lev][1].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
return;
}
if (num.h < Tree[lev][0].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
}
else{
if (Tree[lev][0].h>Tree[lev][1].h){
if (num.h>Tree[lev][1].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
return;
}
if (num.h > Tree[lev][0].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
}
}
void Push(int lev, int l, int r, int x, int y, WALL num){
int mid = (l + r) / 2;
if (r < x || y < l) return;
if (x <= l && r <= y){ g(lev, num); return; }
g(lev * 2, Tree[lev][0]), g(lev * 2, Tree[lev][1]);
g(lev * 2 + 1, Tree[lev][0]), g(lev * 2 + 1, Tree[lev][1]);
Tree[lev][0] = Tree[lev][1] = NONO;
Push(lev * 2, l, mid, x, y, num), Push(lev * 2 + 1, mid + 1, r, x, y, num);
}
int get_h(int lev, int h){
if (lev == 0) return h;
if (Tree[lev][0].op == 1) h = max2(h, Tree[lev][0].h);
if (Tree[lev][0].op == 2) h = min2(h, Tree[lev][0].h);
if (Tree[lev][1].op == 1) h = max2(h, Tree[lev][1].h);
if (Tree[lev][1].op == 2) h = min2(h, Tree[lev][1].h);
return get_h(lev / 2, h);
}
int main(){
WALL temp;
int x, y;
scanf("%d %d", &n, &m), NONO = make_WALL(-1, -1);
for (nn = 1; nn < n; nn *= 2);
for (int i = 1; i < nn * 2; i++) Tree[i][0] = Tree[i][1] = NONO;
for (int i = 1; i <= m; i++){
scanf("%d %d %d %d", &temp.op, &x, &y, &temp.h), x++, y++;
Push(1, 1, nn, x, y, temp);
}
for (int i = 1; i <= n; i++) printf("%d\n", get_h(nn + i - 1, 0));
}