oj.uz

Submission #185461

# Submission time Handle Problem Language Result Execution time Memory
185461 2020-01-11T21:16:35 Z faremy Teams (IOI15_teams) C++14
100 / 100
 1940 ms 296188 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12280 KB Output is correct
2 Correct 16 ms 12024 KB Output is correct
3 Correct 16 ms 12152 KB Output is correct
4 Correct 16 ms 12200 KB Output is correct
5 Correct 15 ms 12152 KB Output is correct
6 Correct 16 ms 12152 KB Output is correct
7 Correct 16 ms 12152 KB Output is correct
8 Correct 17 ms 12028 KB Output is correct
9 Correct 16 ms 12024 KB Output is correct
10 Correct 16 ms 12152 KB Output is correct
11 Correct 12 ms 12052 KB Output is correct
12 Correct 18 ms 12152 KB Output is correct
13 Correct 15 ms 12152 KB Output is correct
14 Correct 16 ms 12024 KB Output is correct
15 Correct 16 ms 12152 KB Output is correct
16 Correct 16 ms 12152 KB Output is correct
17 Correct 16 ms 12024 KB Output is correct
18 Correct 17 ms 12120 KB Output is correct
19 Correct 17 ms 12152 KB Output is correct
20 Correct 17 ms 12024 KB Output is correct
21 Correct 15 ms 12152 KB Output is correct
22 Correct 14 ms 12152 KB Output is correct
23 Correct 14 ms 12152 KB Output is correct
24 Correct 11 ms 12024 KB Output is correct
25 Correct 13 ms 12024 KB Output is correct
26 Correct 14 ms 12028 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 48964 KB Output is correct
2 Correct 137 ms 48964 KB Output is correct
3 Correct 155 ms 49000 KB Output is correct
4 Correct 165 ms 49180 KB Output is correct
5 Correct 46 ms 16648 KB Output is correct
6 Correct 41 ms 16652 KB Output is correct
7 Correct 41 ms 16668 KB Output is correct
8 Correct 41 ms 16756 KB Output is correct
9 Correct 84 ms 16628 KB Output is correct
10 Correct 54 ms 16236 KB Output is correct
11 Correct 43 ms 16340 KB Output is correct
12 Correct 45 ms 16492 KB Output is correct
13 Correct 59 ms 23008 KB Output is correct
14 Correct 74 ms 31536 KB Output is correct
15 Correct 129 ms 48836 KB Output is correct
16 Correct 127 ms 48840 KB Output is correct
17 Correct 50 ms 19048 KB Output is correct
18 Correct 51 ms 19076 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 49156 KB Output is correct
2 Correct 177 ms 49292 KB Output is correct
3 Correct 501 ms 49296 KB Output is correct
4 Correct 166 ms 49096 KB Output is correct
5 Correct 80 ms 17132 KB Output is correct
6 Correct 76 ms 17112 KB Output is correct
7 Correct 51 ms 17132 KB Output is correct
8 Correct 69 ms 17136 KB Output is correct
9 Correct 88 ms 16492 KB Output is correct
10 Correct 128 ms 16364 KB Output is correct
11 Correct 143 ms 16464 KB Output is correct
12 Correct 149 ms 17128 KB Output is correct
13 Correct 243 ms 23340 KB Output is correct
14 Correct 594 ms 48836 KB Output is correct
15 Correct 237 ms 48972 KB Output is correct
16 Correct 233 ms 48892 KB Output is correct
17 Correct 113 ms 19308 KB Output is correct
18 Correct 125 ms 19336 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1129 ms 295904 KB Output is correct
2 Correct 1076 ms 296048 KB Output is correct
3 Correct 1940 ms 296076 KB Output is correct
4 Correct 1134 ms 296188 KB Output is correct
5 Correct 234 ms 34388 KB Output is correct
6 Correct 232 ms 34552 KB Output is correct
7 Correct 169 ms 34396 KB Output is correct
8 Correct 201 ms 34396 KB Output is correct
9 Correct 353 ms 33364 KB Output is correct
10 Correct 323 ms 31572 KB Output is correct
11 Correct 341 ms 32340 KB Output is correct
12 Correct 391 ms 40084 KB Output is correct
13 Correct 884 ms 58056 KB Output is correct
14 Correct 1795 ms 294820 KB Output is correct
15 Correct 820 ms 162400 KB Output is correct
16 Correct 736 ms 162680 KB Output is correct
17 Correct 318 ms 42384 KB Output is correct
18 Correct 328 ms 42632 KB Output is correct