oj.uz

Submission #857038

# Submission time Handle Problem Language Result Execution time Memory
857038 2023-10-05T09:34:31 Z jimmaras132 Wall (IOI14_wall) C++14
100 / 100
 576 ms 132424 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 *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.0 / 8.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 1240 KB Output is correct
6 Correct 4 ms 1200 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 103 ms 13904 KB Output is correct
3 Correct 157 ms 8592 KB Output is correct
4 Correct 375 ms 23556 KB Output is correct
5 Correct 228 ms 24660 KB Output is correct
6 Correct 226 ms 23048 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 852 KB Output is correct
8 Correct 102 ms 14044 KB Output is correct
9 Correct 130 ms 8536 KB Output is correct
10 Correct 390 ms 23556 KB Output is correct
11 Correct 232 ms 24832 KB Output is correct
12 Correct 241 ms 23028 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 108 ms 13888 KB Output is correct
15 Correct 22 ms 2640 KB Output is correct
16 Correct 368 ms 23808 KB Output is correct
17 Correct 238 ms 23164 KB Output is correct
18 Correct 239 ms 23092 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 2 ms 348 KB Output is correct
4 Correct 4 ms 1112 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct
7 Correct 0 ms 672 KB Output is correct
8 Correct 105 ms 13904 KB Output is correct
9 Correct 138 ms 8596 KB Output is correct
10 Correct 369 ms 23596 KB Output is correct
11 Correct 255 ms 24612 KB Output is correct
12 Correct 228 ms 23044 KB Output is correct
13 Correct 1 ms 412 KB Output is correct
14 Correct 120 ms 13956 KB Output is correct
15 Correct 21 ms 2648 KB Output is correct
16 Correct 396 ms 23748 KB Output is correct
17 Correct 232 ms 23132 KB Output is correct
18 Correct 229 ms 23108 KB Output is correct
19 Correct 543 ms 132012 KB Output is correct
20 Correct 553 ms 129768 KB Output is correct
21 Correct 534 ms 132424 KB Output is correct
22 Correct 521 ms 129616 KB Output is correct
23 Correct 524 ms 129760 KB Output is correct
24 Correct 534 ms 129612 KB Output is correct
25 Correct 534 ms 129724 KB Output is correct
26 Correct 576 ms 132228 KB Output is correct
27 Correct 535 ms 132248 KB Output is correct
28 Correct 526 ms 129716 KB Output is correct
29 Correct 535 ms 129620 KB Output is correct
30 Correct 533 ms 129572 KB Output is correct