Submission #145199

#	Time	Username	Problem	Language	Result	Execution time	Memory
145199		ecnerwala	Sky Walking (IOI19_walk)	C++14	100 / 100	423 ms	39476 KiB

walk

#include "walk.h"

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using height_t = pair<ll, int>;

const ll INF = 1e18;

struct height_container {
	set<height_t> alive;
	map<height_t, ll> value;

	ll query(height_t h) {
		ll ans = INF;
		auto it = value.lower_bound(h);
		if (it != value.end()) {
			ans = min(ans, it->second + abs(h.first - it->first.first));
		}
		if (it != value.begin()) {
			--it;
			ans = min(ans, it->second + abs(h.first - it->first.first));
		}
		return ans;
	}

	void insert_line(height_t h, ll v = INF) {
		assert(!alive.count(h));
		alive.insert(h);
		if (v == INF || v >= query(h)) {
			return;
		}
		assert(!value.count(h));
		auto emp = value.emplace(h, v);
		assert(emp.second);
		while (true) {
			auto it = emp.first;
			++it;
			if (it == value.end()) break;
			if (it->second >= emp.first->second + abs(it->first.first - emp.first->first.first)) {
				value.erase(it);
			} else {
				break;
			}
		}
		while (true) {
			auto it = emp.first;
			if (it == value.begin()) break;
			--it;
			if (it->second >= emp.first->second + abs(it->first.first - emp.first->first.first)) {
				value.erase(it);
			} else {
				break;
			}
		}
	}

	void delete_line(height_t h) {
		assert(alive.count(h));

		if (value.count(h)) {
			auto pt = alive.find(h);
			auto nt = pt;
			if (pt != alive.begin()) {
				--pt;
				ll v = query(*pt);
				value.emplace(*pt, v);
			}

			if (nt != alive.end()) {
				++nt;
				if (nt != alive.end()) {
					ll v = query(*nt);
					value.emplace(*nt, v);
				}
			}
			value.erase(h);
		}

		alive.erase(h);
	}

	void insert_all(vector<height_t> v) {
		for (height_t h : v) insert_line(h);
	}
	void delete_all(vector<height_t> v) {
		for (height_t h : v) delete_line(h);
	}

	friend std::ostream& operator << (std::ostream& o, const height_container& h) {
		o << "[";
		for (const auto& it : h.alive) {
			o << "(" << it.first << "," << it.second << ")";
			o << ": ";
			if (h.value.count(it)) {
				o << h.value.at(it);
			} else {
				o << "_";
			}
			o << ", ";
		}
		o << "]";
		return o;
	}
};

ll min_distance(vector<int> X_, vector<int> H_, vector<int> L, vector<int> R, vector<int> Y_, int S, int T) {
	int N = int(X_.size());
	int M = int(Y_.size());

	vector<ll> X(X_.begin(), X_.end());
	vector<height_t> H(N);
	for (int i = 0; i < N; i++) {
		H[i] = {H_[i], i};
	}

	vector<height_t> Y(M);
	for (int e = 0; e < M; e++) {
		Y[e] = {Y_[e], -1-e};
	}

	if (S > T) swap(S, T);
	assert(S < T);

	// peak index
	int P = int(max_element(H.begin() + S, H.begin() + T + 1) - H.begin());
	assert(H[P] >= H[S] && H[P] >= H[T]);

	const height_t BOTTOM = {0, -M-1};
	const height_t TOP = {INF, N};

	vector<vector<height_t>> lefts(N);
	vector<vector<height_t>> rights(N);
	for (int e = 0; e < M; e++) {
		lefts[L[e]].push_back(Y[e]);
		rights[R[e]].push_back(Y[e]);
	}

	priority_queue<height_t, vector<height_t>, greater<height_t>> highEdges;
	for (int e = 0; e < M; e++) {
		highEdges.push(Y[e]);
	}

	if (true) { // left->right only
		if (S == 0 && T == N-1) {
			height_container hc;
			hc.insert_line(BOTTOM, 0);
			rights[S].push_back(BOTTOM);
			lefts[T].push_back(BOTTOM);
			for (int i = 0; i < N; i++) {
				hc.insert_all(lefts[i]);
				hc.delete_all(rights[i]);
			}


			ll ans = hc.query(BOTTOM);
			if (ans == INF) {
				return -1;
			}
			return ans + (X[T] - X[S]);
		} else {
			//return -2;
		}
	}

	height_container sLeft, sRight, tLeft, tRight;
	sLeft.insert_line({0, -M-1}, 0);
	sRight.insert_line({0, -M-1}, 0);
	tLeft.insert_line({0, -M-1}, 0);
	tRight.insert_line({0, -M-1}, 0);

	lefts[S].push_back({0, -M-1});
	rights[S].push_back({0, -M-1});
	lefts[T].push_back({0, -M-1});
	rights[T].push_back({0, -M-1});

	int sl = S, sr = S, tl = T, tr = T;

	ll ans = INF;

	bool crossedMid = false;

	while (true) {
		height_t evtHeight = TOP;
		if (!highEdges.empty()) {
			evtHeight = min(evtHeight, highEdges.top());
		}
		if (sl > 0) {
			evtHeight = min(evtHeight, H[sl]);
		}

		if (!crossedMid) {
			evtHeight = min(evtHeight, H[sr]);
			evtHeight = min(evtHeight, H[tl]);
		}

		if (tr < N-1) {
			evtHeight = min(evtHeight, H[tr]);
		}

		if (evtHeight == TOP) break;

		if (!highEdges.empty() && evtHeight == highEdges.top()) {
			// do the thing
			int e = -1-highEdges.top().second;
			highEdges.pop();

			if (crossedMid) {
				assert(Y[e] > H[P]);
				assert(L[e] < S || L[e] > T);
				assert(R[e] < S || R[e] > T);
				if (L[e] < P && P < R[e]) {
					// just connect the two, it crosses
					ans = min(ans, sLeft.query(Y[e]) + tRight.query(Y[e]) + 2 * (X[S] - X[sl]) + 2 * (X[tr] - X[T]));

					// it's never optimal to go further, so we could just break
					//break;

					sLeft.insert_line(Y[e]);
					tRight.insert_line(Y[e]);
				}
			} else {
				assert(Y[e] <= H[P]);
				if (L[e] <= S && S <= R[e]) {
					ll rval = sRight.query(Y[e]) + 2 * (X[sr] - X[S]);
					ll lval = sLeft.query(Y[e]) + 2 * (X[S] - X[sl]);

					sLeft.insert_line(Y[e], rval);
					sRight.insert_line(Y[e], lval);
				}
				if (L[e] <= T && T <= R[e]) {
					ll rval = tRight.query(Y[e]) + 2 * (X[tr] - X[T]);
					ll lval = tLeft.query(Y[e]) + 2 * (X[T] - X[tl]);

					tLeft.insert_line(Y[e], rval);
					tRight.insert_line(Y[e], lval);
				}
			}
		} else if (!crossedMid && evtHeight == H[P]) {
			assert(sr == P && tl == P);

			for (auto it : sRight.value) {
				ans = min(ans, it.second + tLeft.query(it.first));
			}

			crossedMid = true;
		} else if (sl > 0 && evtHeight == H[sl]) {
			sLeft.delete_all(lefts[sl]);
			--sl;
			sLeft.insert_all(rights[sl]);
		} else if (sr < P && evtHeight == H[sr]) {
			sRight.delete_all(rights[sr]);
			++sr;
			sRight.insert_all(lefts[sr]);
		} else if (tl > P && evtHeight == H[tl]) {
			tLeft.delete_all(lefts[tl]);
			--tl;
			tLeft.insert_all(rights[tl]);
		} else if (tr < N-1 && evtHeight == H[tr]) {
			tRight.delete_all(rights[tr]);
			++tr;
			tRight.insert_all(lefts[tr]);
		} else assert(false);
	}

	//cerr << ans << '\n';

	if (ans == INF) return -1;
	else return ans + (X[T] - X[S]);
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43