Submission #1074934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074934		Elias	Meetings (IOI18_meetings)	C++17	60 / 100	1081 ms	786432 KiB

meetings

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#ifdef _DEBUG
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
									 std::vector<int> R);

#else
#include "meetings.h"
#endif

struct Node
{
	int l, r;
	ll value;

	int left_child;
	int right_child;

	ll best_score;
};

vector<Node> tree;
vector<int> a;

tuple<ll, int, int> construct(int l, int r, map<int, deque<int>> indices, ll value)
{
	if (l >= r)
		return {100000000000000, 0, -1};

	if (value < 0)
		return {100000000000000, 0, -1};

	if (indices[value].size() == 0) {
		indices.erase(value);
		int largest = (*indices.rbegin()).first;
		return construct(l, r, move(indices), largest);
	}

	Node node;
	node.value = value;
	node.l = l;
	node.r = r;

	if (l + 1 == r)
	{
		node.left_child = node.right_child = -1;
		node.best_score = value;
	}
	else
	{
		int mid = indices[value][indices[value].size() / 2];

		map<int, deque<int>> left_indices;
		map<int, deque<int>> right_indices;

		if (mid - l < r - mid)
		{
			right_indices = move(indices);

			for (int i = l; i < mid; i++)
			{
				right_indices[a[i]].pop_front();
				left_indices[a[i]].push_back(i);
			}
			right_indices[a[mid]].pop_front();
		}
		else
		{
			left_indices = move(indices);

			for (int i = r - 1; i > mid; i--)
			{
				left_indices[a[i]].pop_back();
				right_indices[a[i]].push_front(i);
			}
			left_indices[a[mid]].pop_back();
		}

		auto [best_l, size_l, index_l] = construct(l, mid, left_indices, value);
		auto [best_r, size_r, index_r] = construct(mid + 1, r, right_indices, value);

		node.left_child = index_l;
		node.right_child = index_r;

		ll best_score = 100000000000000;

		best_score = min(best_score, value * (size_l + 1) + best_r);
		best_score = min(best_score, value * (size_r + 1) + best_l);
		best_score = min<ll>(best_score, value * (size_l + size_r + 1));
		node.best_score = best_score;
	}

	tree.push_back(node);
	return {node.best_score, node.r - node.l, tree.size() - 1};
}

tuple<ll, int> get(int i, int ql, int qr)
{
	if (i == -1)
		return {100000000000000, 0};

	auto node = tree[i];

	if (ql <= node.l && qr >= node.r)
		return {node.best_score, node.r - node.l};

	if (ql >= node.r || qr <= node.l)
		return {100000000000000, 0};

	if (node.l + 1 == node.r)
		return {node.best_score, 1};

	if (node.left_child != -1)
		if (tree[node.left_child].r >= qr)
			return get(node.left_child, ql, qr);

	if (node.right_child != -1)
		if (tree[node.right_child].l <= ql)
			return get(node.right_child, ql, qr);

	auto [best_l, size_l] = get(node.left_child, ql, qr);
	auto [best_r, size_r] = get(node.right_child, ql, qr);

	ll best_score = 100000000000000;

	best_score = min(best_score, node.value * (size_l + 1) + best_r);
	best_score = min(best_score, node.value * (size_r + 1) + best_l);
	best_score = min<ll>(best_score, node.value * (size_l + size_r + 1));

	return {best_score, size_l + size_r + 1};
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
									 std::vector<int> R)
{

	map<int, deque<int>> indices;

	for (int i = 0; i < H.size(); i++)
	{
		a.push_back(H[i]);
		indices[H[i]].push_back(i);
	}

	auto [best_l, size_l, index_l] = construct(0, H.size(), indices, 100000000000000);

	vector<ll> out;
	for (int i = 0; i < L.size(); i++)
	{
		int l = L[i];
		int r = R[i];

		auto [best_r, size_r] = get(index_l, l, r + 1);

			out.push_back(best_r);
	}
	return out;
}

#ifdef _DEBUG

namespace
{

	int read_int()
	{
		int x;
		if (scanf("%d", &x) != 1)
		{
			fprintf(stderr, "Error while reading input\n");
			exit(1);
		}
		return x;
	}

} // namespace

int main()
{
	int N = read_int();
	int Q = read_int();
	std::vector<int> H(N);
	for (int i = 0; i < N; ++i)
	{
		H[i] = read_int();
	}
	std::vector<int> L(Q), R(Q);
	for (int j = 0; j < Q; ++j)
	{
		L[j] = read_int();
		R[j] = read_int();
	}

	std::vector<long long> C = minimum_costs(H, L, R);
	for (size_t j = 0; j < C.size(); ++j)
	{
		printf("%lld\n", C[j]);
	}
	return 0;
}

#endif

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:143:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  for (int i = 0; i < H.size(); i++)
      |                  ~~^~~~~~~~~~
meetings.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for (int i = 0; i < L.size(); i++)
      |                  ~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40