Submission #837318

#	Time	Username	Problem	Language	Result	Execution time	Memory
837318		Johann	Wiring (IOI17_wiring)	C++14	100 / 100	94 ms	17796 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 1LL << 60;

int N, M;
vi pos, color;
vi dp, intervals;

struct segtree
{
	int size;
	vi arr;
	void init(int _size)
	{
		size = 1;
		while (size < _size)
			size *= 2;
		arr.assign(2 * size, INF);
	}
	void set(int i, ll v)
	{
		i += size;
		arr[i] = v;
		while (i >>= 1 > 0)
			arr[i] = min(arr[2 * i], arr[2 * i + 1]);
	}
	ll query(int l, int r) { return query(l, r, 1, 0, size); }
	ll query(int l, int r, int x, int lx, int rx)
	{
		if (l <= lx && rx <= r)
			return arr[x];
		if (r <= lx || rx <= l)
			return INF;
		int m = (lx + rx) / 2;
		ll a = query(l, r, 2 * x, lx, m);
		ll b = query(l, r, 2 * x + 1, m, rx);
		return min(a, b);
	}
};
segtree segL; // compensation for gap will be done on the left
segtree segR; // compenstation for gap will be on the right <==> this is the pure naive cost

long long min_total_length(std::vector<int> _R, std::vector<int> _B)
{
	N = sz(_R), M = sz(_B);
	int ir = 0, ib = 0;
	while (ir + ib < N + M)
	{
		if (ir == N)
			color.push_back(1), pos.push_back(_B[ib++]);
		else if (ib == M)
			color.push_back(0), pos.push_back(_R[ir++]);
		else
		{
			if (_R[ir] < _B[ib])
				color.push_back(0), pos.push_back(_R[ir++]);
			else
				color.push_back(1), pos.push_back(_B[ib++]);
		}
	}

	int c = -1;
	for (int i = 0; i < sz(color); ++i)
	{
		if (c == color[i])
			continue;
		c = color[i];
		intervals.push_back(i);
	}
	intervals.push_back(sz(color)); // for the end of the last interval

	// init dp
	dp.assign(sz(pos) + 1, INF);
	segL.init(sz(dp));
	segR.init(sz(dp));
	dp[0] = 0; // cost of connection all stuff [0, i) only to the left
	{
		int l = 0, r = intervals[1];
		ll sum = (r - l) * pos[r] - accumulate(pos.begin(), pos.begin() + r, 0LL);
		segR.set(0, sum);
		sum -= (r - l) * (pos[r] - pos[r - 1]);
		segL.set(0, sum);
	}
	// do dp
	for (int j = 1, l, m, r; j < sz(intervals) - 1; ++j)
	{
		l = intervals[j - 1], m = intervals[j], r = intervals[j + 1];

		ll cost = 0;
		ll costComp = 0;
		for (int i = m; i < r; ++i)
		{
			cost += pos[i] - pos[m - 1];
			costComp += pos[i] - pos[m];
			ll tmp;
			int change = max(l, m - (i - m + 1));
			tmp = segL.query(change, m + 1);
			if (tmp != INF)
				dp[i + 1] = min(dp[i + 1], cost + tmp);
			tmp = segR.query(l, change);
			if (tmp != INF)
				dp[i + 1] = min(dp[i + 1], costComp + tmp);
		}
		if (r < sz(pos))
		{
			cost = 0;
			costComp = 0;
			for (int i = r - 1; i >= m; --i)
			{
				if (dp[i + 1] != INF)
					segR.set(i + 1, dp[i + 1] + cost),
						segL.set(i + 1, dp[i + 1] + costComp);
				cost += pos[r] - pos[i];
				costComp += pos[r - 1] - pos[i];
			}
			if (dp[m] != INF)
				segR.set(m, dp[m] + cost),
					segL.set(m, dp[m] + costComp);
		}
	}

	return dp[N + M];
}

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