Submission #185461

#	Time	Username	Problem	Language	Result	Execution time	Memory
185461		faremy	Teams (IOI15_teams)	C++14	100 / 100	1940 ms	296188 KiB

teams

#include "teams.h"

#include <algorithm>
#include <vector>
#include <iostream>


struct Node
{
	Node(int d) : date(d) {}
	Node(const Node &prev, int newDate)
	{
		value = prev.value;
		date = newDate;
		left = prev.left;
		right = prev.right;
	}

	int value = 0, date;
	int left = -1, right = -1;
};

struct Interval
{
	int left, right;
	Interval(int l, int r) : left(l), right(r) {}

	bool IsIncludedIn(const Interval &other) const
	{
		return (other.left <= left && right <= other.right);
	}

	bool IsDisjointFrom(const Interval &other) const
	{
		return (other.right <= left || right <= other.left);
	}

	Interval Left() const
	{
		return Interval(left, (left + right) / 2);
	}

	Interval Right() const
	{
		return Interval((left + right) / 2, right);
	}
};

struct Stop
{
	Stop(int p, int u, int k) : pos(p), used(u), keep(k) {}
	int pos, used, keep;
};


const int MAXN = 5e5 + 1;
int students;

const int LEAVES = 1 << 19;
const Interval ROOTCOVER = { 0, LEAVES };

std::vector<int> interEnds[MAXN];
int root[MAXN];
std::vector<Node> tree;


int makeleft(int node)
{
	if (tree[node].left == -1)
	{
		tree.emplace_back(tree[node].date);
		tree[node].left = (int)tree.size() - 1;
	}
	else if (tree[node].date != tree[tree[node].left].date)
	{
		tree.emplace_back(tree[tree[node].left], tree[node].date);
		tree[node].left = (int)tree.size() - 1;
	}

	return tree[node].left;
}

int getleft(int node)
{
	if (node == -1)
		return -1;
	return tree[node].left;
}

int makeright(int node)
{
	if (tree[node].right == -1)
	{
		tree.emplace_back(tree[node].date);
		tree[node].right = (int)tree.size() - 1;
	}
	else if (tree[node].date != tree[tree[node].right].date)
	{
		tree.emplace_back(tree[tree[node].right], tree[node].date);
		tree[node].right = (int)tree.size() - 1;
	}

	return tree[node].right;
}

int getright(int node)
{
	if (node == -1)
		return -1;
	return tree[node].right;
}

int read(int front, int back)
{
	if (front == -1)
		return 0;
	if (back == -1)
		return tree[front].value;
	return (tree[front].value - tree[back].value);
}

void add(int node, Interval covered, Interval requested)
{
	tree[node].value++;
	if (!covered.IsIncludedIn(requested))
	{
		if (!covered.Left().IsDisjointFrom(requested))
			add(makeleft(node), covered.Left(), requested);
		if (!covered.Right().IsDisjointFrom(requested))
			add(makeright(node), covered.Right(), requested);
	}
}

Stop search(int front, int back, Interval covered, Interval requested, int needed)
{
	if (covered.IsIncludedIn(requested))
	{
		int sum = read(front, back);
		if (sum < needed)
			return Stop(covered.right, sum, 0);
		if (covered.right - covered.left == 1)
			return Stop(covered.left, needed, needed);
	}
	else if (covered.IsDisjointFrom(requested))
	{
		return Stop(covered.left, 0, 0);
	}

	Stop lft = search(getleft(front), getleft(back), covered.Left(), requested, needed);
	if (lft.used == needed)
		return lft;

	Stop rgt = search(getright(front), getright(back), covered.Right(), requested, needed - lft.used);
	return Stop(rgt.pos, lft.used + rgt.used, rgt.keep);
}

void init(int N, int A[], int B[])
{
	students = N;
	for (int iStud = 0; iStud < students; iStud++)
		interEnds[A[iStud]].emplace_back(B[iStud]);

	tree.emplace_back(0);
	for (int iStart = 1; iStart <= students; iStart++)
	{
		tree.emplace_back(tree[root[iStart - 1]], iStart);
		root[iStart] = (int)tree.size() - 1;

		for (int end : interEnds[iStart])
			add(root[iStart], ROOTCOVER, Interval(end, end + 1));
	}
}

int can(int M, int K[])
{
	std::sort(K, K + M);
	std::vector<Stop> stops;

	stops.emplace_back(MAXN, 0, 0);
	for (int iGroup = 0; iGroup < M; iGroup++)
	{
		int needed = K[iGroup], start = K[iGroup];
		while (needed > 0)
		{
			if (stops.empty())
				return 0;
			Stop last = stops.back();

			if (last.pos < start)
			{
				stops.pop_back();
				continue;
			}

			Stop result = search(root[K[iGroup]], root[last.used], ROOTCOVER, Interval(start, last.pos), needed);
			needed -= result.used;


			if (needed == 0)
				stops.emplace_back(result.pos, K[iGroup], result.keep);
			else
			{
				start = last.pos;
				needed += last.keep;
				stops.pop_back();
			}
		}
	}

	return 1;
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23