| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 857028 | jimmaras132 | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdint.h>
#include <malloc.h>
#define MIN(x, y) (((x)<(y))?(x):(y))
#define MAX(x, y) (((x)>(y))?(x):(y))
#define L(id) (id * 2)
#define R(id) (id * 2 + 1)
const int MaxN = 2000001;
const int MaxK = 500001;
typedef struct ST {
int64_t *lo;
int64_t *hi;
int64_t n;
} ST;
static ST *st_allocate_tree(int64_t n) {
ST *st = (ST *)calloc(sizeof(*st), 1);
if(st) {
st->lo = (int64_t *)calloc(sizeof(*st->lo), 4*n);
st->hi = (int64_t *)calloc(sizeof(*st->hi), 4*n);
st->n = n;
}
return st;
}
static void st_combine_nodes(ST *st, int64_t par) {
st->lo[L(par)] = MIN(st->lo[L(par)], st->lo[par]);
st->lo[L(par)] = MAX(st->lo[L(par)], st->hi[par]);
st->hi[L(par)] = MAX(st->hi[L(par)], st->hi[par]);
st->hi[L(par)] = MIN(st->hi[L(par)], st->lo[par]);
st->lo[R(par)] = MIN(st->lo[R(par)], st->lo[par]);
st->lo[R(par)] = MAX(st->lo[R(par)], st->hi[par]);
st->hi[R(par)] = MAX(st->hi[R(par)], st->hi[par]);
st->hi[R(par)] = MIN(st->hi[R(par)], st->lo[par]);
/**
* By resetting the nodes along the path, you make sure that whatever operation
* is present on the parent comes after the operations on its children.
*
* Because:
* 1) If you lower to height h on the child and to height h' on the parent after that, only min(h, h') will take effect.
* 2) If you decrease to height h on the child and then increase to height h' on the parent, with h' > h, then the first operation will lose effect.
* 3) If you increase to height h on the child and then increase to height h' on the parent, only max(h, h') will take effect.
* 4) If you increase to height h on the child and then decrease to height h' on the parent, with h' < h, then the first operation will lose effect.
*/
st->lo[par] = 0x7f7f7f7f7f7f7f7f;
st->hi[par] = 0;
}
ST *ST_new(int64_t n) {
ST *st = st_allocate_tree(n);
if(st) {
memset(st->lo, 0x7f, sizeof(*st->lo) * 4 * n);
memset(st->hi, 0x00, sizeof(*st->hi) * 4 * n);
}
return st;
}
void ST_update_decrease(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
if(ur < l || r < ul) return;
if(ul <= l && r <= ur) {
st->lo[id] = MIN(st->lo[id], h);
st->hi[id] = MIN(st->hi[id], h);
} else {
int64_t mid = (l + r) / 2;
st_combine_nodes(st, id);
ST_update_decrease(st, L(id), l, mid, ul, ur, h);
ST_update_decrease(st, R(id), mid + 1, r, ul, ur, h);
}
}
void ST_update_increase(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
if(ur < l || r < ul) return;
if(ul <= l && r <= ur) {
st->lo[id] = MAX(st->lo[id], h);
st->hi[id] = MAX(st->hi[id], h);
} else {
int64_t mid = (l + r) / 2;
st_combine_nodes(st, id);
ST_update_increase(st, L(id), l, mid, ul, ur, h);
ST_update_increase(st, R(id), mid + 1, r, ul, ur, h);
}
}
void ST_push_everything_down(ST *st, int64_t id, int64_t l, int64_t r, int *r_height) {
if(l == r) {
r_height[l] = MIN(st->lo[id], st->hi[id]);
return;
}
int64_t mid = (l + r) / 2;
st_combine_nodes(st, id);
ST_push_everything_down(st, L(id), l, mid, r_height);
ST_push_everything_down(st, R(id), mid + 1, r_height);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int r_height[]) {
ST *st = ST_new(n+1);
for(int i = 0; i < k; i++) {
(op[i] == 1) ? ST_update_increase(st, 0, 0, n, left[i], right[i], height[i]) :
ST_update_decrease(st, 0, 0, n, left[i], right[i], height[i]);
}
ST_push_everything_down(st, 0, 0, n, r_height);
}