Submission #1077748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077748		Elias	Wiring (IOI17_wiring)	C++17	100 / 100	183 ms	23908 KiB

wiring

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#ifdef _DEBUG
long long min_total_length(std::vector<int> r, std::vector<int> b);
#else
#include "wiring.h"
#endif

ll inf = LLONG_MAX / 10;

template <typename T>
struct LzySegtree
{
	vector<T> b;
	vector<T> updates;
	int n;

	void prop(int l, int r, int i)
	{
		b[i] += updates[i];
		if (l + 1 != r)
		{
			updates[i * 2 + 1] += updates[i];
			updates[i * 2 + 2] += updates[i];
		}
		updates[i] = 0;
	}

	T segUpdate(int l, int r, int i, int ul, int ur, T delta)
	{
		prop(l, r, i);
		if (ul >= r || ur <= l)
			return b[i];
		if (ul <= l && ur >= r)
		{
			updates[i] += delta;
			prop(l, r, i);
			return b[i];
		}
		int m = (l + r) / 2;
		return b[i] = min(segUpdate(l, m, i * 2 + 1, ul, ur, delta), segUpdate(m, r, i * 2 + 2, ul, ur, delta));
	}

	T segGet(int l, int r, int i, int ql, int qr)
	{
		prop(l, r, i);
		if (ql >= r || qr <= l)
			return T(inf);
		if (ql <= l && qr >= r)
			return b[i];
		int m = (l + r) / 2;
		return min(segGet(l, m, i * 2 + 1, ql, qr), segGet(m, r, i * 2 + 2, ql, qr));
	}

	T segBuild(int l, int r, int i, vector<T> &a)
	{
		if (l + 1 == r)
			return b[i] = a[l];
		int m = (l + r) / 2;
		return b[i] = min(segBuild(l, m, i * 2 + 1, a), segBuild(m, r, i * 2 + 2, a));
	}

	LzySegtree(vector<T> a)
	{
		n = a.size();
		b.resize(4 * n, T(inf));
		updates.resize(4 * n, 0);
		segBuild(0, n, 0, a);
	}
};

vector<pair<int, int>> all;
map<int, ll> mem;

/// @brief  Assume r is sorted backwards and b forwards
/// @param r
/// @param b
ll match(vector<int> r, vector<int> b)
{
	int n = r.size();
	int m = b.size();

	ll total = 0;

	for (int i = 0; i < max(n, m); i++)
	{
		ll x = r.back();
		ll y = b.back();

		total += abs(x - y);

		if (r.size() > 1)
			r.pop_back();
		if (b.size() > 1)
			b.pop_back();
	}

	return total;
}

long long solve(int i)
{
	if (mem.count(i))
		return mem[i];

	if (i == all.size())
		return mem[i] = 0;

	vector<int> r;
	vector<int> b;

	int index = i;
	while (index < all.size() && all[index].second == all[i].second)
	{
		r.push_back(all[index].first);
		index++;
	}

	reverse(r.begin(), r.end());

	ll result = inf;

	while (index < all.size() && all[index].second != all[i].second)
	{
		b.push_back(all[index].first);

		ll cost = match(r, b);
		result = min(result, cost + min(solve(index), solve(index + 1)));

		index++;
	}

	return mem[i] = result;
}

long long min_total_length(std::vector<int> r, std::vector<int> b)
{
	all.clear();
	mem.clear();

	int n = r.size();
	int m = b.size();

	for (int i : r)
		all.push_back({i, -1});

	for (int i : b)
		all.push_back({i, 1});

	sort(all.begin(), all.end());

	vector<vector<int>> pockets;
	pockets.push_back({all[0].first});

	int index = all.size() - 1;

	for (int i = 1; i < n + m; i++)
	{
		if (all[i].second != all[i - 1].second)
			pockets.push_back({});
		pockets.back().push_back(all[i].first);
	}

	vector<int> last_pocket;
	vector<ll> last_scores;
	ll last_skip = 0;

	for (int i = pockets.size() - 1; i >= 0; i--)
	{

		int n = pockets[i].size();
		vector<ll> scores(n, inf);

		if (last_pocket.size() > 0)
		{
			vector<int> pocket = pockets[i];

			vector<ll> last1 = last_scores;
			vector<ll> last2 = last_scores;

			last1.pop_back();
			last2.erase(last2.begin());

			assert(last1.size() == last_pocket.size());

			ll additional = 0;
			for (int i = 0; i < last_pocket.size(); i++)
			{
				additional += last_pocket[i] - pocket.back();
				last1[i] += additional;
				last2[i] += additional;
			}

			LzySegtree<ll> segte1(last1);
			LzySegtree<ll> segte2(last2);

			scores[pocket.size() - 1] = min(segte1.segGet(0, segte1.n, 0, 0, segte1.n), segte2.segGet(0, segte2.n, 0, 0, segte2.n));
			// assert(scores[pocket.size() - 1] == solve(index));
			int first_index = pocket.back();
			pocket.pop_back();
			index--;
			int count = 1;

			while (pocket.size())
			{
				int current = pocket.back();
				count++;

				segte1.segUpdate(0, segte1.n, 0, count - 1, segte1.n, first_index - current);
				segte2.segUpdate(0, segte2.n, 0, count - 1, segte2.n, first_index - current);

				segte1.segUpdate(0, segte1.n, 0, 0, count - 1, last_pocket[0] - current);
				segte2.segUpdate(0, segte2.n, 0, 0, count - 1, last_pocket[0] - current);

				scores[pocket.size() - 1] = min(segte1.segGet(0, segte1.n, 0, 0, segte1.n), segte2.segGet(0, segte2.n, 0, 0, segte2.n));
				// assert(scores[pocket.size() - 1] == solve(index));
				pocket.pop_back();
				index--;
			}
		}
		else
		{
			index -= pockets[i].size();
		}

		scores.push_back(last_skip);

		if (last_pocket.size() > 0)
			last_skip = scores[0];
		else
			last_skip = inf;

		last_scores = scores;

		last_pocket = pockets[i];
	}

	// assert(last_scores[0] == solve(0));

	return last_scores[0];
}

#ifdef _DEBUG

int main()
{
	int n, m;

	int cnt;
	cin >> cnt;
	// assert(2 == scanf("%d %d", &n, &m));

	// vector<int> r(n), b(m);
	// for (int i = 0; i < n; i++)
	// 	assert(1 == scanf("%d", &r[i]));
	// for (int i = 0; i < m; i++)
	// 	assert(1 == scanf("%d", &b[i]));

	while (true)
	{

		vector<int> r, b;

		for (int i = 0; i < cnt; i++)
		{
			if (rand() % 2)
			{
				b.push_back(i);
			}
			else
			{
				r.push_back(i);
			}
		}

		assert(r.size() > 0);
		assert(b.size() > 0);

		long long res = min_total_length(r, b);
		printf("%lld\n", res);
	}

	return 0;
}

#endif

Compilation message (stderr)

wiring.cpp: In function 'long long int solve(int)':
wiring.cpp:113:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  if (i == all.size())
      |      ~~^~~~~~~~~~~~~
wiring.cpp:120:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  while (index < all.size() && all[index].second == all[i].second)
      |         ~~~~~~^~~~~~~~~~~~
wiring.cpp:130:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |  while (index < all.size() && all[index].second != all[i].second)
      |         ~~~~~~^~~~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:194:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |    for (int i = 0; i < last_pocket.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45