Submission #966257

#	Time	Username	Problem	Language	Result	Execution time	Memory
966257		raspy	Wall (IOI14_wall)	C++14	100 / 100	620 ms	107604 KiB

wall

#include "wall.h"
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>

#define inf 1000000

using namespace std;

vector<pair<int, int>> sg(8000005, pair<int, int>(0, inf));
int a[2000005];

void propagate(int vz, int l, int d)
{
	if (l == d)
		return;
	int lv = vz*2+1, ds = vz*2+2;
	sg[lv].first = min(sg[lv].first, sg[vz].second);
	sg[lv].second = min(sg[lv].second, sg[vz].second);
	sg[lv].first = max(sg[lv].first, sg[vz].first);
	sg[lv].second = max(sg[lv].second, sg[vz].first);
	sg[ds].first = min(sg[ds].first, sg[vz].second);
	sg[ds].second = min(sg[ds].second, sg[vz].second);
	sg[ds].first = max(sg[ds].first, sg[vz].first);
	sg[ds].second = max(sg[ds].second, sg[vz].first);
	sg[vz] = {0, inf};
}

void updmn(int vz, int l, int d, int i, int j, int hg)
{
	if (i > d || j < l)
		return;
	propagate(vz, l, d);
	if (i <= l && j >= d)
	{
		sg[vz].first = min(sg[vz].first, hg);
		sg[vz].second = min(sg[vz].second, hg);
		return;
	}
	int mid = (l+d)/2;
	updmn(vz*2+1, l, mid, i, min(mid, j), hg);
	updmn(vz*2+2, mid+1, d, max(mid+1, i), j, hg);
}

void updmx(int vz, int l, int d, int i, int j, int hg)
{
	if (i > d || j < l)
		return;
	if (i <= l && j >= d)
	{
		sg[vz].first = max(sg[vz].first, hg);
		sg[vz].second = max(sg[vz].second, hg);
		return;
	}
	propagate(vz, l, d);
	int mid = (l+d)/2;
	updmx(vz*2+1, l, mid, i, min(mid, j), hg);
	updmx(vz*2+2, mid+1, d, max(mid+1, i), j, hg);
}

void izpis(int vz, int l, int d)
{
	propagate(vz, l, d);
	if (l == d)
	{
		a[l] = sg[vz].first;
		return;
	}
	int mid = (l+d)/2;
	izpis(vz*2+1, l, mid);
	izpis(vz*2+2, mid+1, d);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for (int i = 0; i < k; i++)
	{
		int l = left[i], r = right[i];
		if (op[i] == 2)
			updmn(0, 0, n-1, l, r, height[i]);
		else
			updmx(0, 0, n-1, l, r, height[i]);
	}
	izpis(0, 0, n-1);
	for (int i = 0; i < n; i++)
		finalHeight[i] = a[i];
	return;
}

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