Submission #779763

#	Time	Username	Problem	Language	Result	Execution time	Memory
779763		zsombor	Wall (IOI14_wall)	C++17	100 / 100	754 ms	142328 KiB

wall

#include <iostream>
#include <vector>
//#include "wall.h"
using namespace std;

struct node {
	int L, M, R, MN, MX;
	node() { MN = 0; MX = 1e5; }
};

vector <node> sgt(5e6, node());
vector <int> ans(2e6);

void build_sgt(int x, int l, int r) {
	sgt[x].L = l;
	sgt[x].M = (l + r) / 2;
	sgt[x].R = r;
	if (r - l == 1) { sgt[x].MX = 0; return; }
	build_sgt(2 * x, l, (l + r) / 2);
	build_sgt(2 * x + 1, (l + r) / 2, r);
}

void update_node(int x, int mn, int mx) {
	if (mx < sgt[x].MN) { sgt[x].MN = sgt[x].MX = mx; return; }
	if (mn > sgt[x].MX) { sgt[x].MN = sgt[x].MX = mn; return; }
	sgt[x].MN = max(sgt[x].MN, mn);
	sgt[x].MX = min(sgt[x].MX, mx);
}

void push_down(int x) {
	if (sgt[x].R - sgt[x].L == 1) return;
	update_node(2 * x, sgt[x].MN, sgt[x].MX);
	update_node(2 * x + 1, sgt[x].MN, sgt[x].MX);
	sgt[x].MN = 0;
	sgt[x].MX = 1e5;
}

void update(int x, int l, int r, int mn, int mx) {
	push_down(x);
	if (r <= sgt[x].L || sgt[x].R <= l) return;
	if (l <= sgt[x].L && sgt[x].R <= r) { update_node(x, mn, mx); return; }
	update(2 * x, l, r, mn, mx);
	update(2 * x + 1, l, r, mn, mx);
}

void get_ans(int x) {
	if (sgt[x].R - sgt[x].L == 1) { ans[sgt[x].L] = sgt[x].MN; return; }
	push_down(x);
	get_ans(2 * x);
	get_ans(2 * x + 1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	build_sgt(1, 0, n);
	for (int i = 0; i < k; i++) {
		if (op[i] == 1) update(1, left[i], right[i] + 1, height[i], 1e5);
		else update(1, left[i], right[i] + 1, 0, height[i]);
	}
	get_ans(1);
	for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
}

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