Submission #168189

#	Time	Username	Problem	Language	Result	Execution time	Memory
168189		johutha	Wall (IOI14_wall)	C++14	100 / 100	2375 ms	152056 KiB

wall

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

using namespace std;

struct operation
{
	int minb = -1e9, maxb = 1e9, fixed = -1;

	int apply(int old)
	{
		if (fixed != -1) return fixed;
		return min(maxb, max(minb, old));
	}
};

operation merge(operation o1, operation o2) // o2 after o1
{
	if (o2.fixed != -1)
	{
		return operation{(int)-1e9, (int)1e9, o2.fixed};
	}
	else if (o1.fixed != -1)
	{
		return operation{(int)-1e9, (int)1e9, min(o2.maxb, max(o2.minb, o1.fixed))};
	}

	operation res;
	res.minb = max(o1.minb, o2.minb);
	res.maxb = min(o1.maxb, o2.maxb);

	if (res.maxb <= res.minb)
	{
		res.fixed = (res.minb == o2.minb ? o2.minb : o2.maxb);
		res.minb = -1e9;
		res.maxb = 1e9;
	}

	return res;
}

struct segtree
{
	vector<int> table;
	vector<operation> ops;

	void apply(int pos, operation op)
	{
		ops[pos] = merge(ops[pos], op);
		table[pos] = op.apply(table[pos]);
	}

	void propagate(int pos)
	{
		apply(2*pos + 1, ops[pos]);
		apply(2*pos + 2, ops[pos]);
		ops[pos] = operation();
	}

	void update(int ql, int qr, operation op, int l, int r, int pos)
	{
		if (ql <= l && r <= qr)
		{
			apply(pos, op);
			return;
		}
		if (r < ql || qr < l) return;
		propagate(pos);
		update(ql, qr, op, l, (l + r)/2, 2*pos + 1);
		update(ql, qr, op, (l + r)/2 + 1, r, 2*pos + 2);
	}

	int query(int k, int l, int r, int pos)
	{
		if (l == r) return table[pos];
		propagate(pos);
		if (k <= (l + r)/2) return query(k, l, (l + r)/2, 2*pos + 1);
		else return query(k, (l + r)/2 + 1, r, 2*pos + 2);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	segtree st;
	st.ops.resize(4*n);
	st.table.resize(4*n);

	for (int i = 0; i < k; i++)
	{
		operation nop;
		if (op[i] == 1) nop.minb = height[i];
		else nop.maxb = height[i];
		st.update(left[i], right[i], nop, 0, n - 1, 0);
	}

	for (int i = 0; i < n; i++)
	{
		finalHeight[i] = st.query(i, 0, n - 1, 0);
	}
}

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