Submission #521620

#	Time	Username	Problem	Language	Result	Execution time	Memory
521620		tkwiatkowski	Wiring (IOI17_wiring)	C++17	100 / 100	126 ms	10524 KiB

wiring

/*
	Zadanie: Wiring
	Autor: Tomasz Kwiatkowski
*/

#include <bits/stdc++.h>
#include "wiring.h"
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;

const int BASE = 1<<17;

long long segTree[2*BASE + 7];
long long lazy[2*BASE + 7];

void Update(int v)
{
	segTree[2*v] += lazy[v];
	segTree[2*v + 1] += lazy[v];
	lazy[2*v] += lazy[v];
	lazy[2*v + 1] += lazy[v];
	lazy[v] = 0;
}

void Add(int a, int b, long long val, int v = 1, int l = 0, int r = BASE - 1)
{
	if (b < l || r < a)
		return;
	if (a <= l && r <= b) {
		segTree[v] += val;
		lazy[v] += val;
		return;
	}
	Update(v);
	int mid = (l + r) / 2;
	Add(a, b, val, 2*v, l, mid);
	Add(a, b, val, 2*v + 1, mid + 1, r);
	segTree[v] = min(segTree[2*v], segTree[2*v + 1]);
}

void Clear(int a, int b, int v = 1, int l = 0, int r = BASE - 1)
{
	segTree[v] = 1e18;
	lazy[v] = 0;
	if (l == r)
		return;

	int mid = (l + r) / 2;
	if (l <= b)
		Clear(a, b, 2*v, l, mid);
	if (mid + 1 <= b)
		Clear(a, b, 2*v + 1, mid + 1, r);
}

long long min_total_length(vector<int> r, vector<int> b)
{
	for (int i = 0; i < 2*BASE; ++i)
		segTree[i] = 1e18, lazy[i] = 0;

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

	int i, j;
	i = j = 0;
	vector<int> x;
	vector<bool> col;
	while (i < n && j < m)
		col.pb(r[i] < b[j]), x.pb((r[i] < b[j] ? r[i++] : b[j++]));
	while (i < n)
		col.pb(1), x.pb(r[i++]);
	while (j < m)
		col.pb(0), x.pb(b[j++]);

	segTree[1] = 0;
	long long ans = 0;
	int prv_k = 0;
	x.pb(x.back());
	col.pb(!col.back());
	for (int i = 0; i < n+m;) {
		//printf("starting: i = %d\n", i);
		int d = (i ? x[i] - x[i - 1] : 0);
		int j = i;
		int k = 0;
		vector<long long> dp;
		dp.pb(segTree[1]);
		//printf(" dp: %lld\n", dp.back());
		long long sum = 0;
		long long tmp = 0;
		while (j < n+m && col[j] == col[i]) {
			++k;
			Add(k, prv_k, -d);
			
			dp.pb(tmp + segTree[1]);
			//printf(" dp: %lld + %lld\n", tmp, segTree[1]);
			if (col[j + 1] == col[i]) {
				sum += x[j + 1] - x[j];
				//printf(" sum = %lld\n", sum);
				tmp += sum;
			}
			++j;
		}
		Clear(0, prv_k + 1);
		tmp = 0;
		sum = 0;
		ans = dp[dp.size()-1] + tmp + (ll)(dp.size()-1)*d;
		for (size_t a = 0; a < dp.size(); ++a) {
			Add(a, a, -(ll)1e18 + dp[dp.size()-1 - a] + tmp + (ll)a*(x[j] - x[j - 1]) + (ll)(dp.size()-1 - a)*d);
			//printf(" Add %lu: %lld + %lld + %lld + %lld\n", a, dp[dp.size()-1 - a], (ll)a*(x[j] - x[j - 1]), tmp, (ll)(dp.size()-1 - a)*d);
			if (a > 0) {
				sum += x[j - a] - x[j - a - 1];
				tmp += sum;
			}
		}
		prv_k = dp.size();
		i = j;
	}
	return ans;
}

// int main()
// {
// 	ios_base::sync_with_stdio(0), cin.tie(0);



// 	return 0;
// }

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