Submission #831186

#	Time	Username	Problem	Language	Result	Execution time	Memory
831186		PurpleCrayon	Sky Walking (IOI19_walk)	C++17	33 / 100	263 ms	49312 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 = 6e5+10;
const ll INF = 1e18+10;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

int n, m;
vector<pair<int, ll>> adj[N];
ll dist[N], extra[N]; // extra cost for the nodes

void add_edge(int a, int b, ll w) {
	// cerr << "add: " << a << ' ' << b << ' ' << w << endl;
	adj[a].emplace_back(b, w);
	adj[b].emplace_back(a, w);
}

void dijkstra(int S) {
	fill(dist, dist + N, INF);
	for (int a = 0; a < N; a++) {
		for (auto& [b, w] : adj[a]) {
			w += extra[b];
		}
	}

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

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = sz(x), m = sz(l);

	
	vector<int> nl, nr, ny;
	for (int i = 0; i < m; i++) {
		if (l[i] < s && r[i] > s) {
			bool has = 0;
			for (int j = s; j <= g; j++) if (h[j] >= y[i]) {
				has = 1;
			}

			if (!has) {
				int one = s;
				int two = g;
				while (h[one] < y[i]) one--;
				while (h[two] < y[i]) two++;
				l[i] = one, r[i] = two;
				extra[sz(nl)] += x[s] - x[l[i]] + x[r[i]] - x[g];
				nl.push_back(l[i]);
				nr.push_back(r[i]);
				ny.push_back(y[i]);
				continue;
			}
		}

		if (l[i] < s && r[i] >= s) {
			int one = s-1;
			while (one >= l[i] && h[one] < y[i]) one--;
			int two = s;
			while (two <= r[i] && h[two] < y[i]) two++;

			// [l, one]
			// [one, two] -> extra of x[s] - x[one]
			// l[i] = two

			// cerr << "> " << one << ' ' << l[i] << ' ' << two << endl;
			if (l[i] < one) { nl.push_back(l[i]); nr.push_back(one); ny.push_back(y[i]); }
			if (one < two && two <= r[i]) {
				// cerr << "extra: " << sz(nl) << ' ' << x[s] - x[one] << endl;
				extra[sz(nl)] += x[s] - x[one];
				nl.push_back(one); nr.push_back(two); ny.push_back(y[i]);
			}

			l[i] = two;
		}

		if (r[i] > g && l[i] <= g) {
			int one = g+1;
			while (one <= r[i] && h[one] < y[i]) one++;
			int two = g;
			while (two >= l[i] && h[two] < y[i]) two--;

			// [one, r]
			// [two, one] -> extra of x[one] - x[g]
			// r[i] = two

			if (one < r[i]) { nl.push_back(one); nr.push_back(r[i]); ny.push_back(y[i]); }
			if (two < one && two >= l[i]) {
				extra[sz(nl)] += x[one] - x[g];
				nl.push_back(two), nr.push_back(one), ny.push_back(y[i]);
			}

			r[i] = two;
		}

		if (l[i] < r[i]) {
			nl.push_back(l[i]);
			nr.push_back(r[i]);
			ny.push_back(y[i]);
		}
	}

	// cout << sz(l) << ' ' << sz(r) << ' ' << sz(y) << endl;
	swap(l, nl); swap(r, nr); swap(y, ny);
	// cout << sz(l) << ' ' << sz(r) << ' ' << sz(y) << endl;
	m = sz(l);
	// for (int i = 0; i < m; i++) {
	// 	cerr << l[i] << ' ' << r[i] << ' ' << y[i] << ' ' << extra[i] << endl;
	// }
	// s = 0;

	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;

				if (y[x] <= h[i]) {
					auto it = next(me);
					if (it != s.end() && it->first <= h[i]) {
						// cerr << "h1\n";
						add_edge(x, it->second, it->first - y[x]);
					}
				}

				if (y[x] <= h[i]) {
					if (me != s.begin()) {
						auto it = prev(me);
						// cerr << "h2\n";
						add_edge(x, it->second, y[x] - it->first);
					}
				}
			}

			for (int x : ev[i]) if (on[x]) {
				auto me = s.find({y[x], x});
				if (y[x] <= h[i]) {
					auto it = next(me);
					if (it != s.end() && it->first <= h[i]) {
						// cerr << "h3\n";
						add_edge(x, it->second, it->first - y[x]);
					}
				}

				if (y[x] <= h[i]) {
					if (me != s.begin()) {
						// cerr << "h3\n";
						auto it = prev(me);
						add_edge(x, it->second, y[x] - it->first);
					}
				}

				s.erase(me);
			}

			for (int x : ev[i]) on[x] = !on[x];
		}
	};

	build();
	int S = m;
	for (int i = 0; i < m; i++) {
		// cerr << "> " << l[i] << ' ' << s << ' ' << r[i] << ' ' << y[i] << ' ' << h[s] << endl;
		if (l[i] <= s && s <= r[i] && y[i] <= h[s]) {
			add_edge(S, i, y[i]);
		}
	}
	dijkstra(S);

	ll ans = INF;
	for (int i = 0; i < m; i++) {
		
		if (l[i] <= g && g <= r[i] && y[i] <= h[g]) {
			ans = min(ans, dist[i] + y[i]);
		}
	}
	// cerr << "base: " << ans << endl;

	// 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