Submission #421475

#	Time	Username	Problem	Language	Result	Execution time	Memory
421475		Mlxa	Sky Walking (IOI19_walk)	C++14	100 / 100	2495 ms	203976 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 T    = 1 << 17;
const int N    = 1 << 20;
const int INF  = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3fLL;
const int NONE = -19;

struct str_1 {
	str_1() {
		fill_n(ass, 2 * T, NONE);
	}
	int ass[2 * T];
	int ls(int v) {
		return 2 * v + 1;
	}
	int rs(int v) {
		return 2 * v + 2;
	}
	void push(int v) {
		if (ass[v] == NONE) {
			return;
		}
		ass[ls(v)] = ass[rs(v)] = ass[v];
		ass[v] = NONE;
	}
	void upd(int v, int vl, int vr, int ql, int qr, int val) {
		if (ql <= vl && vr <= qr) {
			ass[v] = val;
			return;
		}
		if (qr <= vl || vr <= ql) {
			return;
		}
		int vm = (vl + vr) / 2;
		push(v);
		upd(ls(v), vl, vm, ql, qr, val);
		upd(rs(v), vm, vr, ql, qr, val);
	}
	void upd(int l, int r, int v) {
		// for (int i = l; i <= r; ++i) {
		// 	arr[i] = v;
		// }
		upd(0, 0, T, l, r + 1, v);
	}
	int query(int v, int vl, int vr, int pos) {
		assert(vl <= pos && pos < vr);
		if (vr - vl == 1) {
			return ass[v];
		}
		int vm = (vl + vr) / 2;
		push(v);
		if (pos < vm) {
			return query(ls(v), vl, vm, pos);
		} else {
			return query(rs(v), vm, vr, pos);
		}
	}
	int query(int i) {
		// return arr[i];
		return query(0, 0, T, i);
	}
	
} assigner;

struct str_2 {
	int mx[2 * T];
	void upd(int i, int v) {
		mx[i += T] = v;
		for (i /= 2; i > 0; i /= 2) {
			mx[i] = max(mx[i + i], mx[i + i + 1]);
		}
	}
	int to_rig(int v, int vl, int vr, int pos, int val) {
		// cout << "to_rig " << v << " " << vl << " " << vr << " " << pos << " " << val << endl;
		if (mx[v] < val || vr <= pos) {
			return -1;
		}
		if (vr - vl == 1) {
			assert(vl >= pos && mx[v] >= val);
			return vl;
		}
		int vm = (vl + vr) / 2;
		int res = to_rig(v + v, vl, vm, pos, val);
		if (res != -1) {
			return res;
		}
		return to_rig(v + v + 1, vm, vr, pos, val);
	}
	int to_rig(int pos, int val) {
		return to_rig(1, 0, T, pos, val);
		while (mx[T + pos] < val) {
			++pos;
		}
		return pos;
	}
	int to_lef(int v, int vl, int vr, int pos, int val) {
		if (mx[v] < val || vl > pos) {
			return -1;
		}
		if (vr - vl == 1) {
			assert(vl <= pos && mx[v] >= val);
			return vl;
		}
		int vm = (vl + vr) / 2;
		int res = to_lef(v + v + 1, vm, vr, pos, val);
		if (res != -1) {
			return res;
		}
		return to_lef(v + v, vl, vm, pos, val);
	}
	int to_lef(int i, int v) {
		return to_lef(1, 0, T, i, v);
	}
} 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);
			// cout << e.l << " " << a << " " << b << " " << e.r << endl;
			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: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43