Submission #1222676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222676		AmirAli_H1	Wiring (IOI17_wiring)	C++17	100 / 100	67 ms	12460 KiB

wiring

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 18) + 4;
const ll oo = 1e18 + 4;

int n; vector<pll> A; vector<pii> ls;
ll dp[maxn]; vector<int> ls0, ls1;
pll t[2 * maxn]; ll valx[maxn];

void build(int v, int tl, int tr) {
	t[v].F = 0;
	if (tr - tl == 1) {
		t[v].S = valx[tl];
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v].S = min(t[2 * v + 1].S, t[2 * v + 2].S) + t[v].F;
}

void add_val(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl || r <= l) return ;
	if (l == tl && r == tr) {
		t[v].F += x; t[v].S += x;
		return ;
	}
	int mid = (tl + tr) / 2;
	add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
	t[v].S = min(t[2 * v + 1].S, t[2 * v + 2].S) + t[v].F;
}

ll calx(int l, int r) {
	ls0.clear(); ls1.clear();
	for (int i = l; i < r; i++) {
		if (A[i].S == 0) ls0.pb(i);
		else ls1.pb(i);
	}
	if (len(ls0) == 0 || len(ls1) == 0) return oo;
	if (ls0[0] > ls1[0]) swap(ls0, ls1);
	reverse(all(ls1));
	while (len(ls0) < len(ls1)) ls0.pb(ls0.back());
	while (len(ls1) < len(ls0)) ls1.pb(ls1.back());
	ll res = 0;
	for (int i = 0; i < len(ls0); i++) res += (A[ls1[i]].F - A[ls0[i]].F);
	return res;
}

ll min_total_length(vector<int> rx, vector<int> bx) {
	n = len(rx) + len(bx); A.pb(Mp(-1, -1));
	for (int i = 0; i < len(rx); i++) A.pb(Mp(rx[i], 0));
	for (int i = 0; i < len(bx); i++) A.pb(Mp(bx[i], 1));
	sort(all(A));

	int j = 1;
	for (int i = 1; i <= n; i++) {
		if (A[i].S != A[j].S) {
			ls.pb(Mp(j, i));
			j = i;
		}
	}
	ls.pb(Mp(j, n + 1));

	fill(dp, dp + (n + 1), oo); dp[0] = 0;
	for (int d = 1; d < len(ls); d++) {
		int l = ls[d].F, r = ls[d].S;
		int lx = ls[d - 1].F, rx = ls[d - 1].S;
		ll sm = 0;
		for (int j = rx - 1; j >= lx; j--) {
			sm += abs(A[j].F - A[l].F);
			valx[j] = min(dp[j], dp[j - 1]) + sm;
		}
		build(0, lx, rx);
		for (int i = l; i < r; i++) {
			dp[i] = t[0].S;
			if (i + 1 < r) {
				int jx = (i - l) + 1;
				ll R1 = abs(A[i + 1].F - A[rx - 1].F);
				ll R2 = abs(A[i + 1].F - A[l].F);
				add_val(0, lx, rx, rx - jx, rx, R1);
				add_val(0, lx, rx, lx, rx - jx, R2);
			}
		}
	}
	return dp[n];
}

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