제출 #861056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861056		MongHwa	벽 (IOI14_wall)	C++17	100 / 100	755 ms	59340 KiB

wall

#include <wall.h>
#include <vector>
#include <cmath>
using namespace std;

#define X first
#define Y second
#define INF 0x7f7f7f7f

int idx;

void init(vector<pair<int, int>>& lazy, int node, int start, int end)
{
	if(start == end)
		lazy[node] = {0, INF};
	else
	{
		init(lazy, node*2, start, (start+end)/2);
		init(lazy, node*2+1, (start+end)/2+1, end);
		lazy[node] = {0, INF};
	}
}

void update_lazy(vector<pair<int, int>>& lazy, int node, int start, int end)
{
	if(start != end)
	{
		lazy[node*2].X = max(lazy[node*2].X, lazy[node].X);
		lazy[node*2].Y = max(lazy[node*2].Y, lazy[node].X);
		lazy[node*2+1].X = max(lazy[node*2+1].X, lazy[node].X);
		lazy[node*2+1].Y = max(lazy[node*2+1].Y, lazy[node].X);

		lazy[node*2].X = min(lazy[node*2].X, lazy[node].Y);
		lazy[node*2].Y = min(lazy[node*2].Y, lazy[node].Y);
		lazy[node*2+1].X = min(lazy[node*2+1].X, lazy[node].Y);
		lazy[node*2+1].Y = min(lazy[node*2+1].Y, lazy[node].Y);

		lazy[node] = {0, INF};
	}
}

void update_range(vector<pair<int, int>>& lazy, int node, int start, int end, int left, int right, int type, int val)
{
	update_lazy(lazy, node, start, end);
	if(right < start || left > end)
		return;
	if(left <= start && end <= right)
	{
		if(type == 1)
		{
			lazy[node].X = max(lazy[node].X, val);
			lazy[node].Y = max(lazy[node].Y, val);
		}
		else if(type == 2)
		{
			lazy[node].X = min(lazy[node].X, val);
			lazy[node].Y = min(lazy[node].Y, val);
		}
		update_lazy(lazy, node, start, end);
		return;
	}

	update_range(lazy, node*2, start, (start+end)/2, left, right, type, val);
	update_range(lazy, node*2+1, (start+end)/2+1, end, left, right, type, val);
}

void ans(vector<pair<int, int>>& lazy, int result[], int node, int start, int end)
{
	update_lazy(lazy, node, start, end);
	if(start == end)
		result[idx++] = lazy[node].X;
	else
	{
		ans(lazy, result, node*2, start, (start+end)/2);
		ans(lazy, result, node*2+1, (start+end)/2+1, end);
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	int h = (int)ceil(log2(n));
	int tree_size = (1<<(h+1));
	vector<pair<int, int>> lazy(tree_size);

	init(lazy, 1, 0, n-1);

	for(int i = 0; i < k; i++)
		update_range(lazy, 1, 0, n-1, left[i], right[i], op[i], height[i]);

	ans(lazy, finalHeight, 1, 0, n-1);
}

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