Submission #670356

#	Time	Username	Problem	Language	Result	Execution time	Memory
670356		Eae02	Wiring (IOI17_wiring)	C++17	100 / 100	68 ms	17952 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define all(x) begin(x), end(x)

struct SegTree {
	using T = ll;
	T f(T a, T b) { return min(a, b); }
	static constexpr T UNIT = LLONG_MAX;//neutral value for f
	
	vector<T> s; ll n;
	SegTree(ll len) : s(2 * len, UNIT), n(len) {}
	void set(ll pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(ll lo, ll hi) { // hi not included
		T ra = UNIT, rb = UNIT;
		for (lo+=n, hi+=n; lo < hi; lo/=2, hi/=2) {
			if (lo % 2) ra = f(ra, s[lo++]);
			if (hi % 2) rb = f(s[--hi], rb);
		}
		return f(ra, rb);
	}
};

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector<pair<ll, ll>> pts;
	for (int x : r)
		pts.emplace_back(x, 1);
	for (int x : b)
		pts.emplace_back(x, 0);
	sort(all(pts));
	
	vector<ll> nextDiffColorUp(pts.size());
	nextDiffColorUp.back() = -1;
	for (ll i = (ll)pts.size() - 2; i >= 0; i--) {
		if (pts[i].second != pts[i + 1].second) {
			nextDiffColorUp[i] = i + 1;
		} else {
			nextDiffColorUp[i] = nextDiffColorUp[i + 1];
		}
	}
	
	vector<ll> nextDiffColorDown(pts.size());
	nextDiffColorDown[0] = -1;
	for (ll i = 1; i < (ll)pts.size(); i++) {
		if (pts[i].second != pts[i - 1].second) {
			nextDiffColorDown[i] = i - 1;
		} else {
			nextDiffColorDown[i] = nextDiffColorDown[i - 1];
		}
	}
	
	vector<ll> sumDown(pts.size(), 0);
	for (ll i = 1; i < (ll)pts.size(); i++) {
		if (pts[i].second != pts[i - 1].second) {
			sumDown[i] = 0;
		} else if (nextDiffColorDown[i] == -1) {
			sumDown[i] = 1E9;
		} else {
			ll dest = nextDiffColorDown[i] + 1;
			sumDown[i] = sumDown[i - 1] + (pts[i].first - pts[dest].first);
		}
	}
	
	vector<ll> sumUp(pts.size(), 0);
	for (ll i = (ll)pts.size() - 2; i >= 0; i--) {
		if (pts[i].second != pts[i + 1].second) {
			sumUp[i] = pts[i + 1].first - pts[i].first;
		} else if (nextDiffColorUp[i] == -1) {
			sumUp[i] = 1E9;
		} else {
			ll dest = nextDiffColorUp[i];
			sumUp[i] = sumUp[i + 1] + (pts[dest].first - pts[i].first);
		}
	}
	
	SegTree st(pts.size() + 1); // st[j] = dp[j] + sumDown[j - 1]
	st.set(pts.size(), 0 + sumDown[pts.size() - 1]);
	vector<ll> dp(pts.size() + 1, 0);
	for (ll i = (ll)pts.size() - 1; i >= 0; i--) {
		ll ans = LLONG_MAX;
		if (nextDiffColorDown[i] != -1) {
			ans = dp[i + 1] + (pts[i].first - pts[nextDiffColorDown[i]].first);
		}
		if (nextDiffColorUp[i] != -1) {
			ll nextSegmentEndPlus1 = nextDiffColorUp[nextDiffColorUp[i]];
			if (nextSegmentEndPlus1 == -1)
				nextSegmentEndPlus1 = pts.size();
			ll lenNextSegment = nextSegmentEndPlus1 - nextDiffColorUp[i];
			ll maxL = min(
				nextDiffColorUp[i] - i, // how many remaining in this segment
				lenNextSegment
			);
			//for (ll L = 1; L <= maxL; L++) {
			//	ans = min(ans, dp[nextDiffColorUp[i] + L] + sumUp[i] + sumDown[nextDiffColorUp[i] + L - 1]);
			//}
			ll rangeAns = st.query(nextDiffColorUp[i] + 1, nextDiffColorUp[i] + maxL + 1);
			//for (ll j = nextDiffColorUp[i] + 1; j <= nextDiffColorUp[i] + maxL; j++) {
			//	rangeAns = min(rangeAns, dp[j] + sumDown[j - 1]);
			//}
			if (rangeAns != LLONG_MAX)
				ans = min(rangeAns + sumUp[i], ans);
		}
		dp[i] = ans;
		if (i != 0)
			st.set(i, dp[i] + sumDown[i - 1]);
	}
	
	return dp[0];
}

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