Submission #857026

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
857026	2023-10-05T09:11:17 Z	jimmaras132	Wall (IOI14_wall)	C++14	Compilation error	0 ms	0 KB

wall

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.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[n] = min(st->hi[n], 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[n] = max(st->hi[n], 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);
	ST_push_everything_down(st, R(id), mid + 1);
}
 
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:14:2: error: 'int64_t' does not name a type
   14 |  int64_t *lo;
      |  ^~~~~~~
wall.cpp:15:2: error: 'int64_t' does not name a type
   15 |  int64_t *hi;
      |  ^~~~~~~
wall.cpp:16:2: error: 'int64_t' does not name a type
   16 |  int64_t n;
      |  ^~~~~~~
wall.cpp:19:29: error: 'int64_t' was not declared in this scope
   19 | static ST *st_allocate_tree(int64_t n) {
      |                             ^~~~~~~
wall.cpp:29:38: error: 'int64_t' has not been declared
   29 | static void st_combine_nodes(ST *st, int64_t par) {
      |                                      ^~~~~~~
wall.cpp: In function 'void st_combine_nodes(ST*, int)':
wall.cpp:30:6: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   30 |  st->lo[L(par)] = MIN(st->lo[L(par)], st->lo[par]);
      |      ^~
wall.cpp:30:27: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   30 |  st->lo[L(par)] = MIN(st->lo[L(par)], st->lo[par]);
      |                           ^~
wall.cpp:4:22: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                      ^
wall.cpp:30:43: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   30 |  st->lo[L(par)] = MIN(st->lo[L(par)], st->lo[par]);
      |                                           ^~
wall.cpp:4:26: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                          ^
wall.cpp:30:27: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   30 |  st->lo[L(par)] = MIN(st->lo[L(par)], st->lo[par]);
      |                           ^~
wall.cpp:4:31: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                               ^
wall.cpp:30:43: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   30 |  st->lo[L(par)] = MIN(st->lo[L(par)], st->lo[par]);
      |                                           ^~
wall.cpp:4:35: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                                   ^
wall.cpp:31:6: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   31 |  st->lo[L(par)] = MAX(st->lo[L(par)], st->hi[par]);
      |      ^~
wall.cpp:31:27: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   31 |  st->lo[L(par)] = MAX(st->lo[L(par)], st->hi[par]);
      |                           ^~
wall.cpp:5:22: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                      ^
wall.cpp:31:43: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   31 |  st->lo[L(par)] = MAX(st->lo[L(par)], st->hi[par]);
      |                                           ^~
wall.cpp:5:26: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                          ^
wall.cpp:31:27: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   31 |  st->lo[L(par)] = MAX(st->lo[L(par)], st->hi[par]);
      |                           ^~
wall.cpp:5:31: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                               ^
wall.cpp:31:43: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   31 |  st->lo[L(par)] = MAX(st->lo[L(par)], st->hi[par]);
      |                                           ^~
wall.cpp:5:35: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                                   ^
wall.cpp:32:6: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   32 |  st->hi[L(par)] = MAX(st->hi[L(par)], st->hi[par]);
      |      ^~
wall.cpp:32:27: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   32 |  st->hi[L(par)] = MAX(st->hi[L(par)], st->hi[par]);
      |                           ^~
wall.cpp:5:22: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                      ^
wall.cpp:32:43: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   32 |  st->hi[L(par)] = MAX(st->hi[L(par)], st->hi[par]);
      |                                           ^~
wall.cpp:5:26: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                          ^
wall.cpp:32:27: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   32 |  st->hi[L(par)] = MAX(st->hi[L(par)], st->hi[par]);
      |                           ^~
wall.cpp:5:31: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                               ^
wall.cpp:32:43: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   32 |  st->hi[L(par)] = MAX(st->hi[L(par)], st->hi[par]);
      |                                           ^~
wall.cpp:5:35: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                                   ^
wall.cpp:33:6: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   33 |  st->hi[L(par)] = MIN(st->hi[L(par)], st->lo[par]);
      |      ^~
wall.cpp:33:27: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   33 |  st->hi[L(par)] = MIN(st->hi[L(par)], st->lo[par]);
      |                           ^~
wall.cpp:4:22: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                      ^
wall.cpp:33:43: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   33 |  st->hi[L(par)] = MIN(st->hi[L(par)], st->lo[par]);
      |                                           ^~
wall.cpp:4:26: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                          ^
wall.cpp:33:27: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   33 |  st->hi[L(par)] = MIN(st->hi[L(par)], st->lo[par]);
      |                           ^~
wall.cpp:4:31: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                               ^
wall.cpp:33:43: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   33 |  st->hi[L(par)] = MIN(st->hi[L(par)], st->lo[par]);
      |                                           ^~
wall.cpp:4:35: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                                   ^
wall.cpp:35:6: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   35 |  st->lo[R(par)] = MIN(st->lo[R(par)], st->lo[par]);
      |      ^~
wall.cpp:35:27: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   35 |  st->lo[R(par)] = MIN(st->lo[R(par)], st->lo[par]);
      |                           ^~
wall.cpp:4:22: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                      ^
wall.cpp:35:43: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   35 |  st->lo[R(par)] = MIN(st->lo[R(par)], st->lo[par]);
      |                                           ^~
wall.cpp:4:26: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                          ^
wall.cpp:35:27: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   35 |  st->lo[R(par)] = MIN(st->lo[R(par)], st->lo[par]);
      |                           ^~
wall.cpp:4:31: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                               ^
wall.cpp:35:43: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   35 |  st->lo[R(par)] = MIN(st->lo[R(par)], st->lo[par]);
      |                                           ^~
wall.cpp:4:35: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                                   ^
wall.cpp:36:6: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   36 |  st->lo[R(par)] = MAX(st->lo[R(par)], st->hi[par]);
      |      ^~
wall.cpp:36:27: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   36 |  st->lo[R(par)] = MAX(st->lo[R(par)], st->hi[par]);
      |                           ^~
wall.cpp:5:22: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                      ^
wall.cpp:36:43: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   36 |  st->lo[R(par)] = MAX(st->lo[R(par)], st->hi[par]);
      |                                           ^~
wall.cpp:5:26: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                          ^
wall.cpp:36:27: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   36 |  st->lo[R(par)] = MAX(st->lo[R(par)], st->hi[par]);
      |                           ^~
wall.cpp:5:31: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                               ^
wall.cpp:36:43: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   36 |  st->lo[R(par)] = MAX(st->lo[R(par)], st->hi[par]);
      |                                           ^~
wall.cpp:5:35: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                                   ^
wall.cpp:37:6: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   37 |  st->hi[R(par)] = MAX(st->hi[R(par)], st->hi[par]);
      |      ^~
wall.cpp:37:27: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   37 |  st->hi[R(par)] = MAX(st->hi[R(par)], st->hi[par]);
      |                           ^~
wall.cpp:5:22: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                      ^
wall.cpp:37:43: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   37 |  st->hi[R(par)] = MAX(st->hi[R(par)], st->hi[par]);
      |                                           ^~
wall.cpp:5:26: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                          ^
wall.cpp:37:27: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   37 |  st->hi[R(par)] = MAX(st->hi[R(par)], st->hi[par]);
      |                           ^~
wall.cpp:5:31: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                               ^
wall.cpp:37:43: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   37 |  st->hi[R(par)] = MAX(st->hi[R(par)], st->hi[par]);
      |                                           ^~
wall.cpp:5:35: note: in definition of macro 'MAX'
    5 | #define MAX(x, y) (((x)>(y))?(x):(y))
      |                                   ^
wall.cpp:38:6: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   38 |  st->hi[R(par)] = MIN(st->hi[R(par)], st->lo[par]);
      |      ^~
wall.cpp:38:27: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   38 |  st->hi[R(par)] = MIN(st->hi[R(par)], st->lo[par]);
      |                           ^~
wall.cpp:4:22: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                      ^
wall.cpp:38:43: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   38 |  st->hi[R(par)] = MIN(st->hi[R(par)], st->lo[par]);
      |                                           ^~
wall.cpp:4:26: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                          ^
wall.cpp:38:27: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   38 |  st->hi[R(par)] = MIN(st->hi[R(par)], st->lo[par]);
      |                           ^~
wall.cpp:4:31: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                               ^
wall.cpp:38:43: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   38 |  st->hi[R(par)] = MIN(st->hi[R(par)], st->lo[par]);
      |                                           ^~
wall.cpp:4:35: note: in definition of macro 'MIN'
    4 | #define MIN(x, y) (((x)<(y))?(x):(y))
      |                                   ^
wall.cpp:50:6: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   50 |  st->lo[par] = 0x7f7f7f7f7f7f7f7f;
      |      ^~
wall.cpp:51:6: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   51 |  st->hi[par] = 0;
      |      ^~
wall.cpp: At global scope:
wall.cpp:54:12: error: 'int64_t' was not declared in this scope
   54 | ST *ST_new(int64_t n) {
      |            ^~~~~~~
wall.cpp:63:33: error: 'int64_t' has not been declared
   63 | void ST_update_decrease(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                 ^~~~~~~
wall.cpp:63:45: error: 'int64_t' has not been declared
   63 | void ST_update_decrease(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                             ^~~~~~~
wall.cpp:63:56: error: 'int64_t' has not been declared
   63 | void ST_update_decrease(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                                        ^~~~~~~
wall.cpp:63:67: error: 'int64_t' has not been declared
   63 | void ST_update_decrease(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                                                   ^~~~~~~
wall.cpp:63:79: error: 'int64_t' has not been declared
   63 | void ST_update_decrease(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                                                               ^~~~~~~
wall.cpp:63:91: error: 'int64_t' has not been declared
   63 | void ST_update_decrease(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                                                                           ^~~~~~~
wall.cpp: In function 'void ST_update_decrease(ST*, int, int, int, int, int, int)':
wall.cpp:66:7: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   66 |   st->lo[id] = min(st->lo[id], h);
      |       ^~
wall.cpp:66:24: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   66 |   st->lo[id] = min(st->lo[id], h);
      |                        ^~
wall.cpp:66:16: error: 'min' was not declared in this scope
   66 |   st->lo[id] = min(st->lo[id], h);
      |                ^~~
wall.cpp:67:13: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   67 |         st->hi[n] = min(st->hi[n], h);
      |             ^~
wall.cpp:67:16: error: 'n' was not declared in this scope
   67 |         st->hi[n] = min(st->hi[n], h);
      |                ^
wall.cpp:67:29: error: 'ST' {aka 'struct ST'} has no member named 'hi'
   67 |         st->hi[n] = min(st->hi[n], h);
      |                             ^~
wall.cpp:69:3: error: 'int64_t' was not declared in this scope
   69 |   int64_t mid = (l + r) / 2;
      |   ^~~~~~~
wall.cpp:71:36: error: 'mid' was not declared in this scope; did you mean 'id'?
   71 |   ST_update_decrease(st, L(id), l, mid, ul, ur, h);
      |                                    ^~~
      |                                    id
wall.cpp: At global scope:
wall.cpp:76:33: error: 'int64_t' has not been declared
   76 | void ST_update_increase(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                 ^~~~~~~
wall.cpp:76:45: error: 'int64_t' has not been declared
   76 | void ST_update_increase(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                             ^~~~~~~
wall.cpp:76:56: error: 'int64_t' has not been declared
   76 | void ST_update_increase(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                                        ^~~~~~~
wall.cpp:76:67: error: 'int64_t' has not been declared
   76 | void ST_update_increase(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                                                   ^~~~~~~
wall.cpp:76:79: error: 'int64_t' has not been declared
   76 | void ST_update_increase(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                                                               ^~~~~~~
wall.cpp:76:91: error: 'int64_t' has not been declared
   76 | void ST_update_increase(ST *st, int64_t id, int64_t l, int64_t r, int64_t ul, int64_t ur, int64_t h) {
      |                                                                                           ^~~~~~~
wall.cpp: In function 'void ST_update_increase(ST*, int, int, int, int, int, int)':
wall.cpp:79:7: error: 'ST' {aka 'struct ST'} has no member named 'lo'
   79 |   st->lo[id] = max(st->lo[id], h);
      |       ^~
wall.cpp:79:24: error: 'ST' {ak