Submission #857038

#	Time	Username	Problem	Language	Result	Execution time	Memory
857038		jimmaras132	Wall (IOI14_wall)	C++14	100 / 100	576 ms	132424 KiB

wall

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdint.h>
#include <malloc.h>
#include <string.h>
 
#define MIN(x, y)	(((x)<(y))?(x):(y))
#define MAX(x, y)	(((x)>(y))?(x):(y))

#define L(id)		(id * 2 + 1)
#define R(id)		(id * 2 + 2)
 
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) {
#ifdef DEBUG
		printf("%lld ", MIN(st->lo[id], st->hi[id]));
#else
		r_height[l] = MIN(st->lo[id], st->hi[id]);
#endif
		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, r_height);
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int r_height[]) {
	ST *st = ST_new(n);
	for(int i = 0; i < k; i++) {
#ifdef DEBUG
		printf("%s [%d, %d] %d\n", ((op[i] == 1) ? "increase" : "decrease"), left[i], right[i], height[i]);
#endif
		(op[i] == 1) ? ST_update_increase(st, 0, 0, n - 1, left[i], right[i], height[i]) :
		               ST_update_decrease(st, 0, 0, n - 1, left[i], right[i], height[i]);
	}
	ST_push_everything_down(st, 0, 0, n - 1, r_height);
}

#ifdef DEBUG
int main(void) {
	int op[] = {1, 2, 2, 1, 1, 2};
	int l[] = {1, 4, 3, 0, 2, 6};
	int r[] = {8, 9, 6, 5, 2, 7};
	int h[] = {4, 1, 5, 3, 5, 0};
	buildWall(10, 6, op, l, r, h, NULL);
	printf("\n");
}
#endif

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39