Submission #851136

#	Time	Username	Problem	Language	Result	Execution time	Memory
851136		promitheas	Wall (IOI14_wall)	C++14	0 / 100	110 ms	13904 KiB

wall

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

template<typename T>
T max(T a, T b) {
	return a < b ? b : a;
}
template<typename T>
T min(T a, T b) {
	return a > b ? b : a;
}

class Node {
public:
	Node* left;
	Node* right;
	bool hasLazy = false;
	void Propagate() {
		if (!left)left = new Node();
		if (!right)right = new Node();
		left->lo = max(left->lo, lo);
		left->hi = max(left->hi, hi);
		right->lo = max(right->lo, lo);
		right->hi = max(right->hi, hi);
	}
	Node* L() {
		if (!left)left = new Node();
		if (hasLazy) {
			Propagate();
			hasLazy = false;
		}
		return left;
	}
	Node* R() {
		if (!right)right = new Node();
		if (hasLazy) {
			Propagate();
			hasLazy = false;
		}
		return right;
	}
	int lo;
	int hi;

	void BuildUp(int l, int r, int tl, int tr, int h) {
		if (l == tl && r == tr) {
			lo = max(lo, h); //bring lo to at least h
			hi = max(hi, lo); // hi must be at least lo
			hasLazy = true;
			return;
		}
		int mid = (l + r) >> 1;
		if (tr <= mid) {
			return L()->BuildUp(l, mid, tl, tr, h);
		}
		if (tl > mid) {
			return R()->BuildUp(mid + 1, r, tl, tr, h);
		}
		L()->BuildUp(l, mid, tl, mid, h);
		R()->BuildUp(mid+1,r, mid+1, tr, h);
	}

	void BreakDown(int l, int r, int tl, int tr, int h) {
		if (l == tl && r == tr) {
			hi = min(hi, h);
			lo = min(lo, h);
			hasLazy = true;
			return;
		}
		int mid = (l + r) >> 1;
		if (tr <= mid) {
			return L()->BreakDown(l, mid, tl, tr, h);
		}
		if (tl > mid) {
			return R()->BreakDown(mid + 1, r, tl, tr, h);
		}
		L()->BreakDown(l, mid, tl, mid, h);
		R()->BreakDown(mid + 1, r, mid + 1, tr, h);
	}
	
	int GetVal(int l, int r, int t) {
		if (l == r)
			return lo;
		int mid = (l + r) >> 1;
		if (t <= mid)
			return L()->GetVal(l, mid, t);
		return R()->GetVal(mid+1, r, t);
	}
};

Node* node;

int N;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	node = new Node();
	for (int i = 0; i < k; i++) {
		if (op[i] == 1)
			node->BuildUp(0, n - 1, left[i], right[i], height[i]);
		else
			node->BreakDown(0, n - 1, left[i], right[i], height[i]);
	}
	for (int i = 0; i < n; i++) {
		finalHeight[i] = node->GetVal(0, n - 1, i);
	}
}

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