Submission #421453

#	Time	Username	Problem	Language	Result	Execution time	Memory
421453		Mlxa	Sky Walking (IOI19_walk)	C++14	10 / 100	4049 ms	153312 KiB

walk

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple0
#define x first
#define y second
#include "walk.h"

namespace my {

const int N    = 1 << 20;
const int INF  = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3fLL;

struct str_1 {
	int arr[N];
	void upd(int l, int r, int v) {
		for (int i = l; i <= r; ++i) {
			arr[i] = v;
		}
	}
	int query(int i) {
		return arr[i];
	}
	
} assigner;

struct str_2 {
	int arr[N];
	void upd(int i, int v) {
		arr[i] = v;
	}
	int to_rig(int i, int v) {
		while (i < N && arr[i] < v) {
			++i;
		}
		return i;
	}
	int to_lef(int i, int v) {
		while (i >= 0 && arr[i] < v) {
			--i;
		}
		return i;
	}
} gfinder;

struct walk {
	int l, r, y, i;
	walk(int a, int b, int c) : l(a), r(b), y(c), i(-1) {}
};
bool operator<(walk a, walk b) {
	return a.y < b.y;
}
vector<walk> was;
vector<int> ord[N];
vector<pair<int, int>> pt;
map<pair<int, int>, int> ma;

vector<pair<int, int>> g[N];
ll dist[N];

int _get_id(int x, int y) {
	auto p = make_pair(x, y);
	if (ma.count(p)) {
		return ma[p];
	} else {
		int v = (int)ma.size();
		assert((int)pt.size() < N);
		pt.emplace_back(x, y);
		return ma[p] = v;
	}
	// int i = (int)(find(all(pt), mp(x, y)) - pt.begin());
	// return i;
}

int get_id(int x, int y) {
	int i = _get_id(x, y);
	assert(pt[i].x == x);
	assert(pt[i].y == y);
	return i;
}

void add_edge(int v, int u) {
	assert(pt[v].x == pt[u].x || pt[v].y == pt[u].y);
	if (v == u) {
		return;
	}
	// cout << "edge " << v << " " << u << endl;
	int w = abs(pt[v].x - pt[u].x) + abs(pt[v].y - pt[u].y);
	// cout << "edge " << pt[v].x << " " << pt[v].y << " " << pt[u].x << " " << pt[u].y << " " << w << endl;
	g[v].emplace_back(u, w);
	g[u].emplace_back(v, w);
}

void vert_edge(int x, int i, int j) {
	assert(i != -1);
	// cout << "vert " << x << " " << i << " " << j << endl;
	if (j == -1) {
		int v = get_id(x, was[i].y);
		ord[i].push_back(v);
		return;
	}
	int v = get_id(x, was[i].y);
	int u = get_id(x, was[j].y);

	ord[i].emplace_back(v);
	ord[j].emplace_back(u);
	add_edge(v, u);
}
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int st, int fi) {
	using namespace my;
	int n = (int)x.size(), m = (int)l.size();
	for (int i = 0; i < n; ++i) {
		gfinder.upd(i, h[i]);
	}
	vector<walk> temp;
	for (int i = 0; i < m; ++i) {
		was.emplace_back(l[i], r[i], y[i]);
	}
	was.emplace_back(0, n - 1, 0);
	sort(all(was));
	for (auto e : was) {
		if (e.l <= st && st <= e.r) {
			int a = gfinder.to_lef(st, e.y);
			int b = gfinder.to_rig(st, e.y);
			assert(e.l <= a && a <= b && b <= e.r);
			if (e.l < a) {
				temp.emplace_back(e.l, a, e.y);
			}
			if (a < b) {
				temp.emplace_back(a, b, e.y);
			}
			if (b < e.r) {
				temp.emplace_back(b, e.r, e.y);
			}
		} else {
			temp.push_back(e);
		}
	}
	was = temp;
	temp.clear();
	for (auto e : was) {
		if (e.l <= fi && fi <= e.r) {
			int a = gfinder.to_lef(fi, e.y);
			int b = gfinder.to_rig(fi, e.y);
			assert(e.l <= a && a <= b && b <= e.r);
			if (e.l < a) {
				temp.emplace_back(e.l, a, e.y);
			}
			if (a < b) {
				temp.emplace_back(a, b, e.y);
			}
			if (b < e.r) {
				temp.emplace_back(b, e.r, e.y);
			}
		} else {
			temp.push_back(e);
		}
	}
	was = temp;
	temp.clear();
	assert(is_sorted(all(was)));
	m = (int)was.size();
	for (int i = 0; i < m; ++i) {
		// cout << was[i].l << " " << was[i].r << " " << was[i].y << endl;
		was[i].i = i;
	}

	assigner.upd(0, n - 1, -1);
	for (int i = 0; i < m; ++i) {
		auto e = was[i];
		vert_edge(x[e.l], e.i, assigner.query(e.l));
		vert_edge(x[e.r], e.i, assigner.query(e.r));
		assigner.upd(e.l, e.r, e.i);
	}
	assigner.upd(0, n - 1, -1);
		for (int i = m; i--; ) {
		auto e = was[i];
		int j = assigner.query(e.l);
		if (j != -1 && h[e.l] >= was[j].y) {
			vert_edge(x[e.l], e.i, j);
		}
		j = assigner.query(e.r);
		if (j != -1 && h[e.r] >= was[j].y) {
			vert_edge(x[e.r], e.i, j);
		}
		assigner.upd(e.l, e.r, e.i);
	}
	for (int i = 0; i < m; ++i) {
		if (was[i].y == 0) {
			continue;
		}
		sort(all(ord[i]), [&](int a, int b) {
			return pt[a].x < pt[b].x;
		});
		for (int j = 0; j + 1 < (int)ord[i].size(); ++j) {
			add_edge(ord[i][j], ord[i][j + 1]);
		}
	}

	int from = get_id(x[st], 0), to = get_id(x[fi], 0);
	fill_n(dist, N, LLINF);
	dist[from] = 0;
	using T = pair<ll, int>;
	priority_queue<T, vector<T>, greater<T>> q;
	q.emplace(dist[from], from);
	// cout << "from " << pt[from].x << " " << pt[from].y << endl;
	// cout << "to   " << pt[to].x << " " << pt[to].y << endl;
	while (q.size()) {
		ll d;
		int v;
		tie(d, v) = q.top(); q.pop();
		if (dist[v] != d) {
			continue;
		}
		for (auto e : g[v]) {
			int u = e.x, w = e.y;
			if (dist[u] > dist[v] + w) {
				dist[u] = dist[v] + w;
				q.emplace(dist[u], u);
			}
		}
	}
	if (dist[to] > LLINF / 2) {
		return -1;
	} else {
		return dist[to];
	}
}

#ifdef LC
#include "grader.cpp"
#endif

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