Submission #831257

#	Time	Username	Problem	Language	Result	Execution time	Memory
831257		PurpleCrayon	Sky Walking (IOI19_walk)	C++17	33 / 100	247 ms	37568 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10;
const ll INF = 1e18+10;
 
template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

struct Solver {
	int n, m;
	vector<pair<int, int>> adj[N];
	ll dist[N];

	void clear() {
		for (int i = 0; i < N; i++) adj[i].clear();
	}
	
	void add_edge(int a, int b, int w) {
		adj[a].emplace_back(b, w);
		adj[b].emplace_back(a, w);
	}
	
	void dijkstra(int S) {
		fill(dist, dist + N, INF);
	
		min_pq<pair<ll, int>> pq;
		pq.push({dist[S] = 0, S});
	
		while (!pq.empty()) {
			auto [d_c, c] = pq.top(); pq.pop();
			if (dist[c] != d_c) continue;
			for (auto [nxt, w] : adj[c]) {
				if (dist[nxt] > dist[c] + w) {
					dist[nxt] = dist[c] + w;
					pq.push({dist[nxt], nxt});
				}
			}
		}
	}
	
	template <class T>
	vector<ll> solve(vector<int> h, vector<int> l, vector<int> r, vector<int> y, vector<T> base) {
		n = sz(h), m = sz(l);
		
		auto build = [&]() {
			vector<vector<int>> ev(n);
			for (int i = 0; i < m; i++) {
				ev[l[i]].push_back(i);
				ev[r[i]].push_back(i);
			}
	
			vector<bool> on(m);
			set<pair<int, int>> s;
			for (int i = 0; i < n; i++) {
				for (int x : ev[i]) if (!on[x]) {
					auto me = s.insert({y[x], x}).first;
	
					{
						auto it = next(me);
						if (it != s.end() && it->first <= h[i]) {
							add_edge(x, it->second, it->first - y[x]);
						}
					}
	
					{
						if (me != s.begin()) {
							auto it = prev(me);
							add_edge(x, it->second, y[x] - it->first);
						}
					}
				}
	
				for (int x : ev[i]) if (on[x]) {
					auto me = s.find({y[x], x});
					{
						auto it = next(me);
						if (it != s.end() && it->first <= h[i]) {
							add_edge(x, it->second, it->first - y[x]);
						}
					}
	
					{
						if (me != s.begin()) {
							auto it = prev(me);
							add_edge(x, it->second, y[x] - it->first);
						}
					}
	
					s.erase({y[x], x});
				}
	
				for (int x : ev[i]) on[x] = !on[x];
			}
		};
	
		build();
		int S = m;
		for (int i = 0; i < m; i++) if (l[i] == 0 && base[i] < INF) {
			add_edge(S, i, base[i]);
		}
		dijkstra(S);

		vector<ll> ans(m);
		for (int i = 0; i < m; i++) {
			ans[i] = dist[i];
		}
		return ans;
	}
};


Solver solver;

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n = sz(x), m = sz(l);
	// assert(s == 0 && g == n-1);

	vector<ll> dist_left(m, INF);
	{
		vector<int> nh;
		for (int i = s; i >= 0; i--) {
			nh.push_back(h[i]);
		}

		vector<int> nl, nr, ny, ids;
		for (int i = 0; i < m; i++) if (l[i] <= s) {
			int L = l[i], R = min(s, r[i]);
			while (h[R] < y[i]) R--; // TODO optimize
			dist_left[i] = x[s] - x[R];

			nl.push_back(s - R); nr.push_back(s - L); ny.push_back(y[i]);
			ids.push_back(i);
		}

		solver.clear();
		auto calc = solver.solve(nh, nl, nr, ny, ny);
		for (int i = 0; i < sz(ids); i++) {
			dist_left[ids[i]] += calc[i];
		}
	}

	vector<ll> dist_right(m, INF);
	{
		vector<int> nh;
		for (int i = g; i < n; i++) {
			nh.push_back(h[i]);
		}

		vector<int> nl, nr, ny, ids;
		for (int i = 0; i < m; i++) if (g <= r[i]) {
			int L = max(g, l[i]), R = r[i];
			while (h[L] < y[i]) L++; // TODO optimize
			dist_right[i] = x[L] - x[g];
			// cerr << "> " << dist_right[i] << endl;

			nl.push_back(L - g); nr.push_back(R - g); ny.push_back(y[i]);
			ids.push_back(i);
		}

		solver.clear();
		auto calc = solver.solve(nh, nl, nr, ny, ny);
		for (int i = 0; i < sz(ids); i++) {
			dist_right[ids[i]] += calc[i];
		}
	}

	auto dist_mid = dist_left;
	{
		vector<int> nh;
		for (int i = s; i <= g; i++) {
			nh.push_back(h[i]);
		}

		vector<int> nl, nr, ny, ids;
		vector<ll> base;
		for (int i = 0; i < m; i++) if (r[i] >= s && l[i] <= g) {
			int L = max(s, l[i]), R = min(g, r[i]);
			while (L <= R && h[L] < y[i]) L++;
			while (R >= L && h[R] < y[i]) R--;
			if (L > R) continue;

			nl.push_back(L - s); nr.push_back(R - s); ny.push_back(y[i]);
			ids.push_back(i);
			base.push_back(dist_left[i]);
		}

		solver.clear();
		auto calc = solver.solve(nh, nl, nr, ny, base);
		for (int i = 0; i < sz(ids); i++) {
			int c = ids[i];
			dist_mid[c] = min(dist_mid[c], calc[i]);
		}
	}
	
	// cerr << "dists\n";
	// for (ll x : dist_left) cerr << x << ' ';
	// cerr << endl;

	// for (ll x : dist_mid) cerr << x << ' ';
	// cerr << endl;

	// for (ll x : dist_right) cerr << x << ' ';
	// cerr << endl;
	// cerr << "end dists\n";


	ll ans = INF;
	for (int i = 0; i < m; i++) {
		ans = min(ans, dist_mid[i] + dist_right[i]);
	}

	// cerr << x[n-1] - x[0] << ' ' << ans << endl;
	if (ans >= INF) return -1;
	return ans + x[g] - x[s];
}

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