Submission #136213

#	Time	Username	Problem	Language	Result	Execution time	Memory
136213		mosesmayer	Wall (IOI14_wall)	C++17	100 / 100	1222 ms	162164 KiB

wall

#include "wall.h"
#include <cstdio>
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
typedef long long LL;

const LL LINF = 1000000000LL * 1000000000LL;
const int mxsz = 2e6 + 3;
struct Node{
	LL top, bot;
	Node(){
		top = 0;
		bot = LINF;
	}
	Node operator+ (const Node &r) const{
		Node ret;
		ret.top = max(top, r.top);
		ret.bot = min(bot, r.bot);
		return ret;
	}
};
struct Seg{
	Node st[mxsz << 2];
	void prop(int p, int l, int r){
		if (l == r) return;
		for (int i = (p<<1); i <= (p<<1|1); i++){
			st[i].bot = min(st[i].bot, st[p].bot);
			st[i].bot = max(st[i].bot, st[p].top);
			st[i].top = max(st[i].top, st[p].top);
			st[i].top = min(st[i].top, st[p].bot);
		}
		st[p].top = 0; st[p].bot = LINF;
	}

	void setMax(int i, int j, LL v, int p, int l, int r){
		// remove columns to have at most v bricks
	//	printf("-> %d %d %lld %d %d\n", i, j, v, l, r);
		if (j < l || i > r) return;
		if (i <= l && j >= r){
			st[p].top = min(st[p].top, v);
			st[p].bot = min(st[p].bot, v);
	//		printf("%d %d: %lld %lld\n", l, r, st[p].top, st[p].bot);
			return;
		}
		prop(p, l, r);
		int md = (l + r) >> 1;
		setMax(i, j, v, p<<1, l, md); setMax(i, j, v, p<<1|1, md+1, r);
	//	st[p] = st[p<<1] + st[p<<1|1];
	//	printf("%d %d: %lld %lld\n", l, r, st[p].top, st[p].bot);
	}
	
	void setMin(int i, int j, LL v, int p, int l, int r){
		// add to columns to have at least v bricks
	//	printf("-> %d %d %lld %d %d\n", i, j, v, l, r);
		if (j < l || i > r) return;
		if (i <= l && j >= r){
			st[p].top = max(st[p].top, v);
			st[p].bot = max(st[p].bot, v);
	//		printf("%d %d: %lld %lld\n", l, r, st[p].top, st[p].bot);
			return;
		}
		prop(p, l, r);
		int md = (l + r) >> 1;
		setMin(i, j, v, p<<1, l, md); setMin(i, j, v, p<<1|1, md+1, r);
	//	st[p] = st[p<<1] + st[p<<1|1];
	//	printf("%d %d: %lld %lld\n", l, r, st[p].top, st[p].bot);
	}

	inline LL get(int i, int p, int l, int r){
		if (l == r){
	//		printf("%d %d:  %lld %lld - - - \n", l, r, st[p].top, st[p].bot);
			return min(st[p].top, st[p].bot);
		}
		prop(p, l, r);
		int md = (l + r) >> 1;
		if (i <= md) return get(i, p<<1, l, md);
		return get(i, p<<1|1, md+1, r);
	}	
} seg;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < k; i++){
	//	printf("%d %d %lld %lld\n", op[i], left[i], right[i], height[i]);
		if (op[i] == 1){
			seg.setMin(left[i], right[i], height[i], 1, 0, n-1);
		} else {
			seg.setMax(left[i], right[i], height[i], 1, 0, n-1);
		}
	//	puts("");
	}
	for (int i = 0; i < n; i++){
		finalHeight[i] = seg.get(i, 1, 0, n-1);
	}
	return;
}

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