Submission #607495

#	Time	Username	Problem	Language	Result	Execution time	Memory
607495		Temmie	Sky Walking (IOI19_walk)	C++17	100 / 100	1571 ms	379196 KiB

walk

#include <bits/stdc++.h>

struct SG {
	
	int h, l, r;
	
	SG() { }
	
	SG(int a, int b, int c) : h(a) , l(b) , r(c) { }
	
};

int n, m;
std::vector <std::pair <int, int>> g[2];
std::vector <std::vector <std::pair <int, int>>> gg;
std::vector <std::vector <int>> del[2];
std::vector <int> h;
std::vector <SG> sg;

void fix(int node) {
	std::vector <std::pair <int, int>> dir[2];
	dir[0] = dir[1] = { { h[node], node } };
	for (int i = node + 1; i < n; i++) {
		if (h[i] <= dir[1].back().first) {
			continue;
		}
		dir[1].emplace_back(h[i], i);
	}
	for (int i = node - 1; i >= 0; i--) {
		if (h[i] <= dir[0].back().first) {
			continue;
		}
		dir[0].emplace_back(h[i], i);
	}
	auto cop = sg;
	cop.clear();
	for (const auto& s : sg) {
		if (s.l < node && node < s.r) {
			int lb[2] = {
				(int) (std::lower_bound(dir[0].begin(), dir[0].end(), std::make_pair(s.h, -1)) - dir[0].begin()),
				(int) (std::lower_bound(dir[1].begin(), dir[1].end(), std::make_pair(s.h, -1)) - dir[1].begin())
			};
			if (s.l != dir[0][lb[0]].second) {
				cop.emplace_back(s.h, s.l, dir[0][lb[0]].second);
			}
			if (dir[0][lb[0]].second != dir[1][lb[1]].second) {
				cop.emplace_back(s.h, dir[0][lb[0]].second, dir[1][lb[1]].second);
			}
			if (dir[1][lb[1]].second != s.r) {
				cop.emplace_back(s.h, dir[1][lb[1]].second, s.r);
			}
		} else {
			cop.emplace_back(s);
		}
	}
	sg = cop;
}

long long min_distance(std::vector <int> a, std::vector <int> _h, std::vector <int> l, std::vector <int> r, std::vector <int> y, int f, int t) {
	n = a.size();
	m = l.size();
	sg.resize(m);
	h = _h;
	for (int i = 0; i < m; i++) {
		sg[i] = { y[i], l[i], r[i] };
	}
	fix(f);
	fix(t);
	del[0].resize(4'000'000);
	del[1].resize(4'000'000);
	for (const auto& s : sg) {
		del[0][s.l].emplace_back(s.h);
		del[1][s.r].emplace_back(s.h);
	}
	std::multiset <int> st = { 0 };
	for (int i = 0; i < n; i++) {
		for (int x : del[0][i]) {
			st.insert(x);
		}
		for (int k = 0; k < 2; k++) {
			for (int x : del[k][i]) {
				g[0].emplace_back(a[i], x);
				g[0].emplace_back(a[i], *prev(st.lower_bound(x)));
			}
		}
		for (int x : del[1][i]) {
			st.erase(st.find(x));
		}
	}
	std::sort(g[0].begin(), g[0].end());
	for (auto p : g[0]) {
		if (g[1].empty() || g[1].back() != p) {
			g[1].push_back(p);
		}
	}
	g[0] = g[1];
	g[1].clear();
	for (auto p : g[0]) {
		g[1].emplace_back(p.second, p.first);
	}
	std::sort(g[1].begin(), g[1].end());
	gg.resize(4'000'000);
	for (int i = 1; i < (int) g[0].size(); i++) {
		if (g[0][i - 1].first != g[0][i].first) {
			continue;
		}
		gg[i - 1].emplace_back(i - 0, g[0][i].second - g[0][i - 1].second);
		gg[i - 0].emplace_back(i - 1, g[0][i].second - g[0][i - 1].second);
	}
	for (const auto& s : sg) {
		int lb = std::lower_bound(g[1].begin(), g[1].end(), std::make_pair(s.h, a[s.l])) - g[1].begin();
		while (g[1][lb] != (std::pair <int, int>) { s.h, a[s.r] }) {
			std::pair <int, int> p[2] = {
				{ g[1][lb - 0].second, g[1][lb - 0].first },
				{ g[1][lb + 1].second, g[1][lb + 1].first }
			};
			lb++;
			gg[std::lower_bound(g[0].begin(), g[0].end(), p[0]) - g[0].begin()].emplace_back(std::lower_bound(g[0].begin(), g[0].end(), p[1]) - g[0].begin(), p[1].first - p[0].first);
			gg[std::lower_bound(g[0].begin(), g[0].end(), p[1]) - g[0].begin()].emplace_back(std::lower_bound(g[0].begin(), g[0].end(), p[0]) - g[0].begin(), p[1].first - p[0].first);
		}
	}
	std::vector <long long> dd(4'000'000, 1LL << 60);
	std::priority_queue <std::pair <long long, int>> pq;
	{
		int tmp = std::lower_bound(g[0].begin(), g[0].end(), std::make_pair(a[f], 0)) - g[0].begin();
		if (tmp == (int) g[0].size() || g[0][tmp] != (std::pair <int, int>) { a[f], 0 }) {
			return -1;
		}
		pq.push({ dd[tmp] = 0, tmp });
	}
	while (pq.size()) {
		int v = pq.top().second;
		pq.pop();
		for (auto p : gg[v]) {
			if (dd[p.first] <= dd[v] + p.second) {
				continue;
			}
			dd[p.first] = dd[v] + p.second;
			pq.push({ -dd[p.first], p.first });
		}
	}
	int lb = std::lower_bound(g[0].begin(), g[0].end(), std::make_pair(a[t], 0)) - g[0].begin();
	return lb == (int) g[0].size() || g[0][lb] != (std::pair <int, int>) { a[t], 0 } || dd[lb] == (1LL << 60) ? -1LL : dd[lb];
}

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