oj.uz

Submission #860312

# Submission time Handle Problem Language Result Execution time Memory
860312 2023-10-12T14:29:50 Z promitheas Wall (IOI14_wall) C++14
100 / 100
 561 ms 132464 KB 
#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 *hi;
	int64_t *lo;
	int64_t n;
} ST;

static ST *st_allocate_tree(int64_t n) {
	ST *st = (ST *)calloc(sizeof(*st), 1);
	if(st) {
		st->hi = (int64_t *)calloc(sizeof(*st->hi), 4*n);
		st->lo = (int64_t *)calloc(sizeof(*st->lo), 4*n);
		st->n = n;
	}
	return st;
}

static void st_combine_nodes(ST *st, int64_t par) {
	st->hi[L(par)] = MIN(st->hi[L(par)], st->hi[par]);
	st->hi[L(par)] = MAX(st->hi[L(par)], st->lo[par]);
	st->lo[L(par)] = MAX(st->lo[L(par)], st->lo[par]);
	st->lo[L(par)] = MIN(st->lo[L(par)], st->hi[par]);
	
	st->hi[R(par)] = MIN(st->hi[R(par)], st->hi[par]);
	st->hi[R(par)] = MAX(st->hi[R(par)], st->lo[par]);
	st->lo[R(par)] = MAX(st->lo[R(par)], st->lo[par]);
	st->lo[R(par)] = MIN(st->lo[R(par)], st->hi[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->hi[par] = 0x7f7f7f7f7f7f7f7f;
	st->lo[par] = 0;
}

ST *ST_new(int64_t n) {
	ST *st = st_allocate_tree(n);
	if(st) {
		memset(st->hi, 0x7f, sizeof(*st->hi) * 4 * n);
		memset(st->lo, 0x00, sizeof(*st->lo) * 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->hi[id] = MIN(st->hi[id], h);
        st->lo[id] = MIN(st->lo[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->hi[id] = MAX(st->hi[id], h);
        st->lo[id] = MAX(st->lo[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->hi[id], st->lo[id]));
#else
		r_height[l] = MIN(st->hi[id], st->lo[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++) {
		(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

// cl walls.cpp -DDEBUG & walls.exe

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 420 KB Output is correct
2 Correct 107 ms 13908 KB Output is correct
3 Correct 135 ms 8596 KB Output is correct
4 Correct 382 ms 23552 KB Output is correct
5 Correct 245 ms 24616 KB Output is correct
6 Correct 226 ms 23116 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 560 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 5 ms 1136 KB Output is correct
5 Correct 4 ms 1120 KB Output is correct
6 Correct 4 ms 1200 KB Output is correct
7 Correct 0 ms 352 KB Output is correct
8 Correct 107 ms 14020 KB Output is correct
9 Correct 129 ms 8604 KB Output is correct
10 Correct 381 ms 23640 KB Output is correct
11 Correct 253 ms 24480 KB Output is correct
12 Correct 228 ms 23124 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 109 ms 14252 KB Output is correct
15 Correct 21 ms 2640 KB Output is correct
16 Correct 366 ms 23892 KB Output is correct
17 Correct 230 ms 23260 KB Output is correct
18 Correct 261 ms 23324 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 4 ms 1208 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 103 ms 13908 KB Output is correct
9 Correct 131 ms 8488 KB Output is correct
10 Correct 376 ms 23572 KB Output is correct
11 Correct 232 ms 24656 KB Output is correct
12 Correct 228 ms 23120 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 103 ms 13876 KB Output is correct
15 Correct 21 ms 2640 KB Output is correct
16 Correct 378 ms 23972 KB Output is correct
17 Correct 232 ms 23120 KB Output is correct
18 Correct 230 ms 23340 KB Output is correct
19 Correct 543 ms 132120 KB Output is correct
20 Correct 521 ms 129716 KB Output is correct
21 Correct 533 ms 132464 KB Output is correct
22 Correct 561 ms 129648 KB Output is correct
23 Correct 521 ms 129716 KB Output is correct
24 Correct 524 ms 129712 KB Output is correct
25 Correct 529 ms 129576 KB Output is correct
26 Correct 538 ms 132236 KB Output is correct
27 Correct 537 ms 132388 KB Output is correct
28 Correct 529 ms 129560 KB Output is correct
29 Correct 520 ms 129664 KB Output is correct
30 Correct 519 ms 129836 KB Output is correct