Submission #596472

#	Time	Username	Problem	Language	Result	Execution time	Memory
596472		Elias	Wall (IOI14_wall)	C++17	100 / 100	745 ms	130660 KiB

wall

#include <bits/stdc++.h>

using namespace std;

#ifndef _DEBUG
#include "wall.h"
#endif

template <class T>
istream &operator>>(istream &in, vector<T> &a)
{
	for (auto &x : a)
		in >> x;
	return in;
}

int minusMin(int a, int b)
{
	if (a == -1)
		return b;
	if (b == -1)
		return a;
	return min(a, b);
}

int minusMax(int a, int b)
{
	if (a == -1)
		return b;
	if (b == -1)
		return a;
	return max(a, b);
}

struct Node
{
	int low = -1;
	int high = -1;
	bool first = 0;

	void Apply(Node update)
	{

		if (this->low == -1 && this->high == -1)
		{
			*this = update;
			return;
		}
		if (update.low == -1 && update.high == -1)
			return;

		low = minusMax(low, update.low);
		high = minusMin(high, update.high);

		if (low > high && high != -1)
		{
			low = high = ((low == update.low) ? update.low : update.high);
		}

		bool a = low == update.low && low != -1;
		bool b = high == update.high && high != -1;

		if (a && b)
			first = update.low;
		else if (a)
			first = 0;
		else if (b)
			first = 1;
	}
};

Node emp = {-1, -1, 0};

vector<Node> b;

void updateRange(int l, int r, int i, int ul, int ur, Node up)
{
	if (l >= ur || r <= ul)
		return;
	if (l >= ul && r <= ur)
	{
		b[i].Apply(up);
		return;
	}

	b[i * 2 + 1].Apply(b[i]);
	b[i * 2 + 2].Apply(b[i]);

	b[i] = emp;

	int m = (l + r) / 2;
	updateRange(l, m, i * 2 + 1, ul, ur, up);
	updateRange(m, r, i * 2 + 2, ul, ur, up);
}

void extractValues(int l, int r, int i, int a[])
{
	if (l + 1 == r)
	{
		a[l] = max(b[i].low, 0);
		return;
	}

	b[i * 2 + 1].Apply(b[i]);
	b[i * 2 + 2].Apply(b[i]);

	b[i] = emp;

	int m = (l + r) / 2;
	extractValues(l, m, i * 2 + 1, a);
	extractValues(m, r, i * 2 + 2, a);
}

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

	b = vector<Node>(n * 4, emp);

	for (int i = 0; i < k; i++)
		updateRange(0, n, 0, left[i], right[i] + 1, ((op[i] == 1) ? Node{height[i], -1, 0} : Node{-1, height[i], 1}));

	extractValues(0, n, 0, finalHeight);
}

#ifdef _DEBUG

signed main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int n, k;
	cin >> n >> k;

	vector<int> op, left, right, height;
	op = left = right = height = vector<int>(k);
	cin >> op >> left >> right >> height;

	vector<int> finalHeight(n);

	buildWall(n, k, op, left, right, height, finalHeight);

	for (int &x : finalHeight)
		cout << x << " ";
	cout << "\n";
}

#endif

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