#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);
}
Compilation message
wall.cpp: In function 'ST* ST_new(int64_t)':
wall.cpp:59:3: error: 'memset' was not declared in this scope
59 | memset(st->lo, 0x7f, sizeof(*st->lo) * 4 * n);
| ^~~~~~
wall.cpp:5:1: note: 'memset' is defined in header '<cstring>'; did you forget to '#include <cstring>'?
4 | #include <malloc.h>
+++ |+#include <cstring>
5 |
wall.cpp: In function 'void ST_push_everything_down(ST*, int64_t, int64_t, int64_t, int*)':
wall.cpp:99:46: error: invalid conversion from 'int*' to 'int64_t' {aka 'long int'} [-fpermissive]
99 | ST_push_everything_down(st, R(id), mid + 1, r_height);
| ^~~~~~~~
| |
| int*
wall.cpp:99:54: error: too few arguments to function 'void ST_push_everything_down(ST*, int64_t, int64_t, int64_t, int*)'
99 | ST_push_everything_down(st, R(id), mid + 1, r_height);
| ^
wall.cpp:91:6: note: declared here
91 | void ST_push_everything_down(ST *st, int64_t id, int64_t l, int64_t r, int *r_height) {
| ^~~~~~~~~~~~~~~~~~~~~~~
