Submission #812618

#	Time	Username	Problem	Language	Result	Execution time	Memory
812618		Arturgo	Wall (IOI14_wall)	C++14	100 / 100	1271 ms	69524 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int INFINI = 1000 * 1000 * 1000;

struct Label {
	int mini, maxi;

	Label(int _mini = 0, int _maxi = INFINI) {
		mini = _mini;
		maxi = _maxi;
	}
};

void append_label(Label& lbl, Label f) {
	lbl.mini = max(lbl.mini, f.mini);
	lbl.maxi = max(lbl.mini, lbl.maxi);
	lbl.maxi = min(lbl.maxi, f.maxi);
	lbl.mini = min(lbl.mini, lbl.maxi);
}

Label labels[(1 << 22)];

void push(int n) {
	if(n >= (1 << 21)) return;
	append_label(labels[2 * n], labels[n]);
	append_label(labels[2 * n + 1], labels[n]);
	labels[n] = Label();
}

void update(int l, int r, Label lbl, int n = 1, int ll = 0, int rr = (1 << 21)) {
	push(n);

	if(r <= ll || rr <= l) return;
	
	if(l <= ll && rr <= r) {
		append_label(labels[n], lbl);
		return;
	}

	int mm = (ll + rr) / 2;
	update(l, r, lbl, 2 * n, ll, mm);
	update(l, r, lbl, 2 * n + 1, mm, rr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	for(int iOp = 0;iOp < k;iOp++) {
		int l = left[iOp], r = right[iOp] + 1, h = height[iOp];
		if(op[iOp] == 1) {
			// Adding phase
			update(l, r, {h, INFINI});
		}
		else {
			// Removing phase
			update(l, r, {0, h});
		}
	}

	for(int iPos = 0;iPos < n;iPos++) {
		update(iPos, iPos + 1, {});
		finalHeight[iPos] = labels[(1 << 21) + iPos].mini;
	}
}

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