Submission #138207

#	Time	Username	Problem	Language	Result	Execution time	Memory
138207		Arturgo	Wall (IOI14_wall)	C++14	100 / 100	939 ms	61560 KiB

wall

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

const int INFINI = 1000 * 1000 * 1000;

pair<int, int> bornes[(1 << 22)];

void push(pair<int, int>& init, pair<int, int> modif) {
	init.first = max(init.first, modif.first);
	init.second = max(init.second, init.first);

	init.second = min(init.second, modif.second);
	init.first = min(init.second, init.first);
}

void update(int noeud) {
	if(noeud >= (1 << 21)) {
		return;
	}

	push(bornes[2 * noeud], bornes[noeud]);
	push(bornes[2 * noeud + 1], bornes[noeud]);
	bornes[noeud] = {0, INFINI};
}

void update(int deb, int fin, pair<int, int> borne, int n = 1, int d = 0, int f = (1 << 21)) {
	update(n);

	if(deb >= f || d >= fin)
		return;
	if(deb <= d && f <= fin) {
		push(bornes[n], borne);
		update(n);
		return;
	}

	int m = (d + f) / 2;
	update(deb, fin, borne, 2 * n, d, m);
	update(deb, fin, borne, 2 * n + 1, m, f);
}

void buildWall(int nbSlots, int nbReqs, int op[], int left[], int right[], int height[], int finalHeight[]) {
	for(int iReq = 0;iReq < nbReqs;iReq++) {
		if(op[iReq] == 1) {
			update(left[iReq], right[iReq] + 1, {height[iReq], INFINI});
		}
		else {
			update(left[iReq], right[iReq] + 1, {0, height[iReq]});
		}
	}

	for(int iSommet = 1;iSommet < (1 << 21);iSommet++)
		update(iSommet);

	for(int iSommet = (1 << 21);iSommet < (1 << 21) + nbSlots;iSommet++) {
		finalHeight[iSommet - (1 << 21)] = bornes[iSommet].first;
	}
}

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