Submission #789940

#	Time	Username	Problem	Language	Result	Execution time	Memory
789940		Sohsoh84	Wiring (IOI17_wiring)	C++17	100 / 100	910 ms	21672 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll MAXN = 1e6 + 10;
const ll INF = 1e15 + 10;

int n;
ll dp[MAXN], ps[MAXN], len[MAXN], f[MAXN], ps_f[MAXN];

namespace segment {
	ll sg[MAXN];

	void update(int ind, ll val, int l = 1, int r = n, int v = 1) {
		if (l == r) sg[v] = val;
		else {
			int mid = (l + r) >> 1;
			if (ind <= mid) update(ind, val, l, mid, v << 1);
			else update(ind, val, mid + 1, r, v << 1 | 1);
			sg[v] = min(sg[v << 1], sg[v << 1 | 1]);
		}
	}

	ll query(int ql, int qr, int l = 1, int r = n, int v = 1) {
		if (ql > r || qr < l) return INF;
		if (ql <= l && qr >= r) return sg[v];
		
		int mid = (l + r) >> 1;
		return min(query(ql, qr, l, mid, v << 1),
				query(ql, qr, mid + 1, r, v << 1 | 1));
	}
};

ll min_total_length(vector<int> r, vector<int> b) {
	vector<pll> vec;
	vec.push_back({-1, -1});
	for (int i = 0; i < int(r.size()); i++) vec.push_back({r[i], 0});
	for (int i = 0; i < int(b.size()); i++) vec.push_back({b[i], 1});

	sort(all(vec));
	dp[0] = 0;
	int lst[2] = {0, 0};

	n = int(vec.size()) - 1;
	for (int i = 1; i <= n; i++) {
		auto [x, t] = vec[i];
		lst[t] = i;
	
		ps[i] = ps[i - 1] + x;
		len[i] = (t == vec[i - 1].Y ? len[i - 1] + 1 : 1);

		int ind = lst[t ^ 1];
		int y = vec[ind].X;
		dp[i] = INF;
		if (ind != 0) {	
			dp[i] = dp[i - 1] + x - y;
			if (len[i] <= len[ind]) {	
				ll s1 = ps[i] - ps[ind], s2 = ps[ind] - (ps[ind - len[i]]);
				dp[i] = min(dp[i], dp[ind - len[i]] + s1 - s2);

				int l = ind - len[ind] + 1, r = ind - len[i];
				if (l <= r)
					dp[i] = min(dp[i], s1 - s2 + segment::query(l, r) + ps_f[r]);
			}
		}

		if (i < n && vec[i + 1].Y != t) {

			for (int j = i; j > i - len[i]; j--) {
				f[j] = vec[i + 1].X - vec[j].X;

			}

			ps_f[i - len[i]] = 0;
			for (int j = i - len[i] + 1; j <= i; j++) {
				ps_f[j] = ps_f[j - 1] + f[j];
				segment::update(j, dp[j - 1] - ps_f[j - 1]);	
			}
		}

		debug(dp[i])
	}
	
	return dp[n];
}

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