Submission #31200

#	Time	Username	Problem	Language	Result	Execution time	Memory
31200		14kg	Wall (IOI14_wall)	C++11	100 / 100	1183 ms	141760 KiB

wall

#include "wall.h"
#define N 2000001
#define max2(x,y) (x>y?x:y)
#define min2(x,y) (x<y?x:y)

struct WALL{
	int op, h;
} Tree[N * 4][2], NONO;
int n, nn, m;

WALL make_WALL(int op, int h)
{
	WALL temp;
	temp.op = op, temp.h = h;
	return temp;
}
void g(int lev, WALL num)
{
	if (num.op == -1) return;
	if (Tree[lev][0].op == -1){ Tree[lev][0] = num; return; }
	if (Tree[lev][1].op == -1){ Tree[lev][1] = num; return; }

	if (Tree[lev][0].op == Tree[lev][1].op)
	{
		if (Tree[lev][0].op == 1) Tree[lev][0].h = max2(Tree[lev][0].h, Tree[lev][1].h);
		else Tree[lev][0].h = min2(Tree[lev][0].h, Tree[lev][1].h);
		Tree[lev][1] = num; return;
	}
	if (Tree[lev][1].op == num.op)
	{
		if (num.op == 1) Tree[lev][1].h = max2(Tree[lev][1].h, num.h);
		else Tree[lev][1].h = min2(Tree[lev][1].h, num.h);
		return;
	}

	if (Tree[lev][1].op == 1)
	{
		if (Tree[lev][1].h > Tree[lev][0].h)
		{
			if (num.h < Tree[lev][1].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
			return;
		}
		if (num.h < Tree[lev][0].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
	}
	else
	{
		if (Tree[lev][0].h>Tree[lev][1].h)
		{
			if (num.h>Tree[lev][1].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
			return;
		}
		if (num.h > Tree[lev][0].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
	}
}
void Push(int lev, int l, int r, int x, int y, WALL num)
{
	int mid = (l + r) / 2;
	if (r < x || y < l) return;
	if (x <= l && r <= y){ g(lev, num); return; }

	g(lev * 2, Tree[lev][0]), g(lev * 2, Tree[lev][1]);
	g(lev * 2 + 1, Tree[lev][0]), g(lev * 2 + 1, Tree[lev][1]);
	Tree[lev][0] = Tree[lev][1] = NONO;

	Push(lev * 2, l, mid, x, y, num), Push(lev * 2 + 1, mid + 1, r, x, y, num);
}
int get_h(int lev, int h)
{
	if (lev == 0) return h;

	if (Tree[lev][0].op == 1) h = max2(h, Tree[lev][0].h);
	if (Tree[lev][0].op == 2) h = min2(h, Tree[lev][0].h);
	if (Tree[lev][1].op == 1) h = max2(h, Tree[lev][1].h);
	if (Tree[lev][1].op == 2) h = min2(h, Tree[lev][1].h);
	return get_h(lev / 2, h);
}
void buildWall(int _n, int _m, int _in1[], int _in2[], int _in3[], int _in4[], int out[]){
	WALL temp;
	int x, y;

	n=_n, m=_m, NONO = make_WALL(-1, -1);
	for (nn = 1; nn < n; nn *= 2);
	for (int i = 1; i < nn * 2; i++) Tree[i][0] = Tree[i][1] = NONO;

	for (int i = 1; i <= m; i++){
        temp.op=_in1[i-1], x=_in2[i-1], y=_in3[i-1], temp.h=_in4[i-1];
		x++, y++, Push(1, 1, nn, x, y, temp);
	}
	for (int i = 1; i <= n; i++) out[i-1]=get_h(nn + i - 1, 0);
}

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