Submission #129204

#	Time	Username	Problem	Language	Result	Execution time	Memory
129204		anayk	Wall (IOI14_wall)	C++14	100 / 100	1164 ms	69724 KiB

wall

#include <iostream>

#include "wall.h"

#define MAXN 2000005
#define MAXH 100000

struct data
{
	int low, high;
};

data seg[4*MAXN];
int N;

data add(data x, bool type, int val)
{
	if(type)
		x.high = std::min(x.high, val);
	else
		x.low = std::max(x.low, val);

	if(x.low >= x.high)
	{
		if(type)
			x.low = x.high;
		else
			x.high = x.low;
	}

	return x;
}

void shift(int id)
{
	seg[2*id] = add(seg[2*id], 0, seg[id].low);
	seg[2*id] = add(seg[2*id], 1, seg[id].high);
	seg[2*id+1] = add(seg[2*id+1], 0, seg[id].low);
	seg[2*id+1] = add(seg[2*id+1], 1, seg[id].high);
	seg[id].low = 0;
	seg[id].high = MAXH;
}

void build(int id = 1, int l = 0, int r = N-1)
{
	if(l == r)
	{
		seg[id].low = seg[id].high = 0;
		return;
	}

	seg[id].low = 0;
	seg[id].high = MAXH;
	int m = (l+r)/2;
	build(2*id, l, m);
	build(2*id+1, m+1, r);
}

void update(int x, int y, int type, int val, int id = 1, int l = 0, int r = N-1)
{
	//std::cout << x << " " << y << " " << type << ' ' << val << " " << id << ' ' << l << ' ' << r << std::endl;

	if(y < l || x > r)
		return;

	if(x <= l && r <= y)
	{
		seg[id] = add(seg[id], type, val);
		//std::cout << seg[id].low << " " << seg[id].high << std::endl;
		return;
	}

	shift(id);
	int m = (l+r)/2;
	update(x, y, type, val, 2*id, l, m);
	update(x, y, type, val, 2*id+1, m+1, r);
}

int val(int x, int id = 1, int l = 0, int r = N-1)
{
	if(l == r)
		return seg[id].low;

	shift(id);
	int m = (l+r)/2;
	if(x <= m)
		return val(x, 2*id, l, m);
	else
		return val(x, 2*id+1, m+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	N = n;
	build();

	for(int i = 0; i < k; i++)
	{
		update(left[i], right[i], op[i]-1, height[i]);
	}

	for(int i = 0; i < n; i++)
	{
		finalHeight[i] = val(i);
	}
}

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