Submission #30909

#	Time	Username	Problem	Language	Result	Execution time	Memory
30909		h0ngjun7	Wall (IOI14_wall)	C++14	100 / 100	966 ms	87072 KiB

wall

#include "wall.h"
#include <algorithm>
using namespace std;
 
const int MAXN = 2000005;
 
struct SEG {
	int max, min;
} seg[4 * MAXN];
 
int n;
 
void push(int x) {
	int L = x * 2, R = x * 2 + 1;
	seg[L].min = min(max(seg[L].min, seg[x].min), seg[x].max);
	seg[R].min = min(max(seg[R].min, seg[x].min), seg[x].max);
	seg[L].max = max(min(seg[L].max, seg[x].max), seg[x].min);
	seg[R].max = max(min(seg[R].max, seg[x].max), seg[x].min);
}
 
void query(int x, int s, int e, int l, int r, int h, int op) {
	if (s > e) return;
	if (e < l || r < s) return;
	if (l <= s && e <= r) {
		if (op == 1) {
			seg[x].min = max(seg[x].min, h);
			seg[x].max = max(seg[x].max, h);
		}
		else {
			seg[x].max = min(seg[x].max, h);
			seg[x].min = min(seg[x].min, h);
		}
		return;
	}
	if (s < e) {
		int m = (s + e) / 2;
		push(x);
		query(x * 2, s, m, l, r, h, op);
		query(x * 2 + 1, m + 1, e, l, r, h, op);
		seg[x].max = max(seg[x * 2].max, seg[x * 2 + 1].max);
		seg[x].min = min(seg[x * 2].min, seg[x * 2 + 1].min);
	}
}
 
int ans[MAXN];
void dfs(int x, int s, int e) {
	if (s > e) return;
	if (s == e) {
		ans[s] = seg[x].max;
		return;
	}
	push(x);
	int m = (s + e) / 2;
	dfs(x * 2, s, m);
	dfs(x * 2 + 1, m + 1, e);
}
 
void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	n = _n;
	for (int i = 0; i < k; i++) {
		query(1, 0, n - 1, left[i], right[i], height[i], op[i]);
	}
	dfs(1, 0, n - 1);
	for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
	return;
}

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