Submission #145195

#	Time	Username	Problem	Language	Result	Execution time	Memory
145195		ecnerwala	Sky Walking (IOI19_walk)	C++14	100 / 100	477 ms	47104 KiB

walk

#include "walk.h"

#include<bits/stdc++.h>

namespace {

namespace min_distance_set {

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 (false) { // 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]);
}

} // namespace min_distance_set

namespace min_distance_dijk {

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

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};
	}

	vector<vector<height_t>> needs(N);

	vector<height_t> heights;
	heights.insert(heights.end(), H.begin(), H.end());
	heights.insert(heights.end(), Y.begin(), Y.end());
	sort(heights.begin(), heights.end());
	reverse(heights.begin(), heights.end());

	set<int> posts;
	for (height_t h : heights) {
		if (h.second >= 0) {
			// it's a post
			posts.insert(h.second);
		} else {
			int e = -1-h.second;
			set<int> eNeeds;
			eNeeds.insert(L[e]);
			eNeeds.insert(R[e]);
			for (int p : {S, T}) {
				if (L[e] <= p && p <= R[e]) {
					{
						auto it = posts.lower_bound(p);
						if (it != posts.end()) {
							eNeeds.insert(*it);
						}
					}
					{
						auto it = posts.upper_bound(p);
						if (it != posts.begin()) {
							eNeeds.insert(*--it);
						}
					}
				}
			}
			for (int i : eNeeds) {
				needs[i].push_back(h);
			}
		}
	}

	int V = 0;
	vector<vector<pair<int, ll>>> adj;

	map<height_t, pair<int, int>> prvVert;
	set<height_t> inters;
	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]);
	}

	const height_t SBOTTOM(0, -1-M);
	lefts[S].push_back(SBOTTOM);
	rights[S].push_back(SBOTTOM);
	needs[S].push_back(SBOTTOM);

	const height_t TBOTTOM(0, -1-(M+1));
	lefts[T].push_back(TBOTTOM);
	rights[T].push_back(TBOTTOM);
	needs[T].push_back(TBOTTOM);


	int Svert = -1, Tvert = -1;
	for (int i = 0; i < N; i++) {
		for (height_t h : lefts[i]) {
			inters.insert(h);
		}

		reverse(needs[i].begin(), needs[i].end()); // should now be sorted

		vector<height_t> realNeeds;
		for (height_t h : needs[i]) {
			auto it = inters.find(h);
			assert(it != inters.end());

			auto kt = it;
			if (kt != inters.begin()) {
				--kt;
				if (realNeeds.empty() || realNeeds.back() < *kt) {
					realNeeds.push_back(*kt);
				}
			}

			if (realNeeds.empty() || realNeeds.back() < *it) {
				realNeeds.push_back(*it);
			}

			auto jt = it; ++jt;
			if (jt != inters.end()) {
				if (realNeeds.empty() || realNeeds.back() < *jt) {
					realNeeds.push_back(*jt);
				}
			}
		}

		while (!realNeeds.empty() && realNeeds.back() > H[i]) realNeeds.pop_back();

		assert(V == int(adj.size()));
		adj.resize(V + int(realNeeds.size()));

		for (int z = 0; z < int(realNeeds.size()); z++) {
			height_t h = realNeeds[z];
			int v = V + z;

			auto it = prvVert.find(h);
			if (it != prvVert.end()) {
				int u = it->second.second;
				ll d = X[i] - X[it->second.first];
				adj[v].emplace_back(u, d);
				adj[u].emplace_back(v, d);

				it->second = {i, v};
			} else {
				prvVert.emplace(h, pair<int, int>{i, v});
			}
		}

		for (int z = 0; z+1 < int(realNeeds.size()); z++) {
			assert(realNeeds[z] < realNeeds[z+1]);
			int v = V + z + 1;
			int u = V + z;
			ll d = realNeeds[z+1].first - realNeeds[z].first;
			adj[v].emplace_back(u, d);
			adj[u].emplace_back(v, d);
		}

		if (i == S) {
			assert(!realNeeds.empty());
			assert(realNeeds[0] == SBOTTOM);
			Svert = V + 0;
		}
		if (i == T) {
			assert(!realNeeds.empty());
			assert(realNeeds[0] == TBOTTOM);
			Tvert = V + 0;
		}

		V += int(realNeeds.size());

		for (height_t h : rights[i]) {
			inters.erase(h);
		}
	}

	const ll INF = 1e18;
	vector<ll> dist(V, INF);
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	dist[Svert] = 0;
	pq.emplace(0, Svert);
	while (!pq.empty()) {
		int cur = pq.top().second;
		ll d = pq.top().first;
		pq.pop();
		if (dist[cur] != d) continue;

		if (cur == Tvert) return d;

		for (auto it : adj[cur]) {
			int nxt = it.first;
			ll nd = d + it.second;
			if (nd < dist[nxt]) {
				dist[nxt] = nd;
				pq.emplace(nd, nxt);
			}
		}
	}

	return -1;
}

} // namespace min_distance_dijk

} // anonymous namespace

long long min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int S, int T) {
	if (true) {
		return min_distance_set::min_distance(X, H, L, R, Y, S, T);
	} else {
		return min_distance_dijk::min_distance(X, H, L, R, Y, S, T);
	}
}

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