Submission #932221

#	Time	Username	Problem	Language	Result	Execution time	Memory
932221		siewjh	Sky Walking (IOI19_walk)	C++17	24 / 100	945 ms	257220 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const int MAXND = 1000005;
int hv[MAXN], ind = -1;
vector<int> add;
map<int, int> mp[MAXN];
vector<pair<int, ll>> adj[MAXND];
ll dist[MAXND];
struct node{
	int s, e, m; vector<pair<int, int>> vec;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if (s == e) vec.push_back({hv[s], s});
		else{
			l = new node(s, m); r = new node(m + 1, e);
			auto &lv = l->vec, &rv = r->vec;
			int lind = 0, lsz = lv.size(), rind = 0, rsz = rv.size();
			while (lind < lsz && rind < rsz){
				if (lv[lind].first >= rv[rind].first){
					vec.push_back(lv[lind]);
					lind++;
				}
				else{
					vec.push_back(rv[rind]);
					rind++;
				}
			}
			while (lind < lsz){
				vec.push_back(lv[lind]);
				lind++;
			}
			while (rind < rsz){
				vec.push_back(rv[rind]);
				rind++;
			}
		}
	}
	void query(int x, int y, int h){
		if (x == s && y == e){
			int sz = e - s + 1;
			for (int i = 0; i < sz && vec[i].first >= h; i++) add.push_back(vec[i].second);
			return;
		}
		else if (y <= m) l->query(x, y, h);
		else if (x > m) r->query(x, y, h);
		else{
			l->query(x, m, h); r->query(m + 1, y, h);
		}
	}
};

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	int n = x.size(), m = y.size();
	for (int i = 0; i < n; i++) hv[i] = h[i];
	node *root = new node(0, n - 1);
	mp[s][0] = ++ind; mp[g][0] = ++ind;
	for (int i = 0; i < m; i++){
		add.clear();
		root->query(l[i], r[i], y[i]);
		sort(add.begin(), add.end());
		int prev = -1, px;
		for (int b : add){
			int aind;
			if (mp[b].count(y[i])) aind = mp[b][y[i]];
			else mp[b][y[i]] = aind = ++ind;
			if (prev != -1){
				adj[aind].push_back({prev, x[b] - px});
				adj[prev].push_back({aind, x[b] - px});
			}
			prev = aind; px = x[b];
		}
	}
	for (int i = 0; i < n; i++){
		int prev = -1, ph;
		for (auto &[height, aind] : mp[i]){
			if (prev != -1){
				adj[aind].push_back({prev, height - ph});
				adj[prev].push_back({aind, height - ph});
			}
			prev = aind; ph = height;
		}
	}
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	pq.push({0, 0});
	for (int i = 0; i <= ind; i++) dist[i] = 1e18;
	dist[0] = 0;
	while (!pq.empty()){
		ll d; int i; tie(d, i) = pq.top(); pq.pop();
		if (dist[i] != d) continue;
		if (i == 1) return d;
		for (auto &[nn, nd] : adj[i]){
			if (d + nd < dist[nn]){
				dist[nn] = d + nd;
				pq.push({dist[nn], nn});
			}
		}
	}
	return -1;
}

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