Submission #118203

#	Time	Username	Problem	Language	Result	Execution time	Memory
118203		PeppaPig	Wiring (IOI17_wiring)	C++14	100 / 100	86 ms	17816 KiB

wiring

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

#define pii pair<int, int>
#define x first
#define y second

#define long long long

using namespace std;

const int N = 2e5+5;

void update(long t[], int x, long k) {
	for(t[x += N] = k; x != 1; x >>= 1)
		t[x>>1] = min(t[x], t[x^1]);
}

long query(long t[], int l, int r) {
	long ret = 1e18;
	for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
		if(l & 1) ret = min(ret, t[l++]);
		if(r & 1) ret = min(ret, t[--r]);
	}
	return ret;
}

int n;
int sz_l[N], sz_r[N], pre[N], pos[N];
long sum_l[N], sum_r[N];
long dp[N], t1[N<<1], t2[N<<1];
vector<pii> all;

long min_total_length(vector<int> r, vector<int> b) {
	n = r.size() + b.size();

	for(int i : r) all.emplace_back(i, 0);
	for(int i : b) all.emplace_back(i, 1);
	all.emplace_back(-1e9, -1e9), all.emplace_back(1e9, 1e9);
	sort(all.begin(), all.end());

	for(int i = 1; i <= n; i++) {
		if(all[i].y == all[i-1].y) {
			sz_l[i] = sz_l[i-1];
			pre[i] = pre[i-1];
			sum_l[i] = sum_l[i-1];
		} else pre[i] = i;
		sum_l[i] += all[i].x - all[pre[i]].x;
		++sz_l[i];
	}
	for(int i = n; i; i--) {
		if(all[i].y == all[i + 1].y) {
			sz_r[i] = sz_r[i+1];
			pos[i] = pos[i+1];
			sum_r[i] = sum_r[i+1];
		} else pos[i] = i;
		sum_r[i] += all[pos[i]].x - all[i].x;
		++sz_r[i];
	}

	for(int i = 1; i <= n; i++) {
		dp[i] = 1e18;
		if(pre[i] != 1) {
			int l = pre[pre[i] - 1];
			dp[i] = min(dp[i], query(t1, max(l, pre[i] - sz_l[i]), pre[i]-1) + sum_l[i] + 1ll * sz_l[i] * (all[pre[i]].x - all[pre[i]-1].x));
			dp[i] = min(dp[i], query(t2, l, pre[i] - sz_l[i] - 1) + sum_l[i]);
		}
		update(t1, i, min(dp[i-1], dp[i]) + sum_r[i]);
		update(t2, i, min(dp[i-1], dp[i]) + sum_r[i] + 1ll * sz_r[i] * (all[pos[i]+1].x - all[pos[i]].x));
	}

	return dp[n];
}

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