Submission #168340

#	Time	Username	Problem	Language	Result	Execution time	Memory
168340		faremy	Teams (IOI15_teams)	C++14	0 / 100	1256 ms	524296 KiB

teams

#include "teams.h"

#include <algorithm>
#include <queue>


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 = 0;
	int left = -1, right = -1;
};

class Interval
{
	int left, right;

public:
	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);
	}
};


const int MAXN = 5e5;
int students;

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

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


void add(int node, Interval covered, Interval requested)
{
	if (covered.IsDisjointFrom(requested))
		return;
	tree[node].value++;

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

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

		add(tree[node].left, covered.Left(), requested);
		add(tree[node].right, covered.Right(), requested);
	}
}

int count(int node, Interval covered, Interval requested)
{
	if (node == -1 || covered.IsDisjointFrom(requested))
		return 0;
	if (covered.IsIncludedIn(requested))
		return tree[node].value;
	return (count(tree[node].left, covered.Left(), requested) + count(tree[node].right, covered.Right(), requested));
}

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

	for (int iStart = 0; iStart < students; iStart++)
	{
		if (iStart == 0)
		{
			tree.emplace_back(0);
			root[iStart] = 0;
		}
		else
		{
			tree.emplace_back(tree[root[iStart - 1]], iStart);
			root[iStart] = 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);
	int used = 0, lastSeen = -1;

	for (int iGroup = M - 1; iGroup > -1; iGroup--)
	{
		K[iGroup]--;
		if (iGroup < M - 1)
			used = std::max(0, used - lastSeen + count(root[K[iGroup]], ROOTCOVER, Interval(K[iGroup + 1], students)));

		lastSeen = count(root[K[iGroup]], ROOTCOVER, Interval(K[iGroup], students));
		if (lastSeen - used <= K[iGroup])
			return 0;
		used += K[iGroup] + 1;
	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void add(int, Interval, Interval)':
teams.cpp:73:34: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
    tree[node].left = tree.size() - 1;
                      ~~~~~~~~~~~~^~~
teams.cpp:78:34: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
    tree[node].left = tree.size() - 1;
                      ~~~~~~~~~~~~^~~
teams.cpp:84:35: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
    tree[node].right = tree.size() - 1;
                       ~~~~~~~~~~~~^~~
teams.cpp:89:35: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
    tree[node].right = tree.size() - 1;
                       ~~~~~~~~~~~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:122:31: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
    root[iStart] = tree.size() - 1;
                   ~~~~~~~~~~~~^~~

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