oj.uz

Submission #421458

# Submission time Handle Problem Language Result Execution time Memory
421458 2021-06-09T07:46:04 Z Mlxa Sky Walking (IOI19_walk) C++14
43 / 100
 4000 ms 156504 KB 
#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 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 58692 KB Output is correct
2 Correct 37 ms 58724 KB Output is correct
3 Correct 39 ms 58660 KB Output is correct
4 Correct 34 ms 58688 KB Output is correct
5 Correct 34 ms 58812 KB Output is correct
6 Correct 35 ms 58744 KB Output is correct
7 Correct 35 ms 58780 KB Output is correct
8 Correct 34 ms 58760 KB Output is correct
9 Correct 35 ms 58728 KB Output is correct
10 Correct 35 ms 58692 KB Output is correct
11 Correct 35 ms 58688 KB Output is correct
12 Correct 38 ms 58700 KB Output is correct
13 Correct 36 ms 58808 KB Output is correct
14 Correct 34 ms 58700 KB Output is correct
15 Correct 39 ms 58728 KB Output is correct
16 Correct 35 ms 58788 KB Output is correct
17 Correct 34 ms 58704 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 58700 KB Output is correct
2 Correct 34 ms 58740 KB Output is correct
3 Correct 1365 ms 125236 KB Output is correct
4 Correct 1459 ms 128488 KB Output is correct
5 Correct 1048 ms 113196 KB Output is correct
6 Correct 1634 ms 110572 KB Output is correct
7 Correct 956 ms 113440 KB Output is correct
8 Correct 1367 ms 129676 KB Output is correct
9 Correct 1313 ms 125228 KB Output is correct
10 Correct 1541 ms 131212 KB Output is correct
11 Correct 1365 ms 115652 KB Output is correct
12 Correct 983 ms 108808 KB Output is correct
13 Correct 1451 ms 132688 KB Output is correct
14 Execution timed out 4059 ms 95472 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 75208 KB Output is correct
2 Correct 1136 ms 144024 KB Output is correct
3 Correct 1375 ms 147700 KB Output is correct
4 Correct 1428 ms 150048 KB Output is correct
5 Correct 1540 ms 152336 KB Output is correct
6 Correct 1420 ms 149100 KB Output is correct
7 Correct 683 ms 108060 KB Output is correct
8 Correct 989 ms 112868 KB Output is correct
9 Correct 1262 ms 142208 KB Output is correct
10 Correct 863 ms 122272 KB Output is correct
11 Correct 47 ms 60504 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 75208 KB Output is correct
2 Correct 1136 ms 144024 KB Output is correct
3 Correct 1375 ms 147700 KB Output is correct
4 Correct 1428 ms 150048 KB Output is correct
5 Correct 1540 ms 152336 KB Output is correct
6 Correct 1420 ms 149100 KB Output is correct
7 Correct 683 ms 108060 KB Output is correct
8 Correct 989 ms 112868 KB Output is correct
9 Correct 1262 ms 142208 KB Output is correct
10 Correct 863 ms 122272 KB Output is correct
11 Correct 47 ms 60504 KB Output is correct
12 Correct 1447 ms 149300 KB Output is correct
13 Correct 1334 ms 153704 KB Output is correct
14 Correct 1554 ms 156480 KB Output is correct
15 Correct 1338 ms 142916 KB Output is correct
16 Correct 1376 ms 138248 KB Output is correct
17 Correct 1510 ms 151580 KB Output is correct
18 Correct 1203 ms 143048 KB Output is correct
19 Correct 1525 ms 138240 KB Output is correct
20 Correct 771 ms 107628 KB Output is correct
21 Correct 100 ms 63416 KB Output is correct
22 Correct 1094 ms 131864 KB Output is correct
23 Correct 1109 ms 127424 KB Output is correct
24 Correct 845 ms 113984 KB Output is correct
25 Correct 1166 ms 123564 KB Output is correct
26 Correct 760 ms 108520 KB Output is correct
27 Correct 1682 ms 156504 KB Output is correct
28 Correct 1352 ms 153244 KB Output is correct
29 Correct 1525 ms 149252 KB Output is correct
30 Correct 735 ms 107688 KB Output is correct
31 Correct 1309 ms 142268 KB Output is correct
32 Correct 867 ms 116444 KB Output is correct
33 Correct 859 ms 116900 KB Output is correct
34 Correct 730 ms 118804 KB Output is correct
35 Correct 879 ms 121456 KB Output is correct
36 Correct 1098 ms 114096 KB Output is correct
37 Correct 991 ms 110692 KB Output is correct
38 Correct 931 ms 111612 KB Output is correct
39 Correct 644 ms 116984 KB Output is correct
40 Correct 923 ms 111348 KB Output is correct
41 Correct 988 ms 109456 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 58692 KB Output is correct
2 Correct 37 ms 58724 KB Output is correct
3 Correct 39 ms 58660 KB Output is correct
4 Correct 34 ms 58688 KB Output is correct
5 Correct 34 ms 58812 KB Output is correct
6 Correct 35 ms 58744 KB Output is correct
7 Correct 35 ms 58780 KB Output is correct
8 Correct 34 ms 58760 KB Output is correct
9 Correct 35 ms 58728 KB Output is correct
10 Correct 35 ms 58692 KB Output is correct
11 Correct 35 ms 58688 KB Output is correct
12 Correct 38 ms 58700 KB Output is correct
13 Correct 36 ms 58808 KB Output is correct
14 Correct 34 ms 58700 KB Output is correct
15 Correct 39 ms 58728 KB Output is correct
16 Correct 35 ms 58788 KB Output is correct
17 Correct 34 ms 58704 KB Output is correct
18 Correct 34 ms 58700 KB Output is correct
19 Correct 34 ms 58740 KB Output is correct
20 Correct 1365 ms 125236 KB Output is correct
21 Correct 1459 ms 128488 KB Output is correct
22 Correct 1048 ms 113196 KB Output is correct
23 Correct 1634 ms 110572 KB Output is correct
24 Correct 956 ms 113440 KB Output is correct
25 Correct 1367 ms 129676 KB Output is correct
26 Correct 1313 ms 125228 KB Output is correct
27 Correct 1541 ms 131212 KB Output is correct
28 Correct 1365 ms 115652 KB Output is correct
29 Correct 983 ms 108808 KB Output is correct
30 Correct 1451 ms 132688 KB Output is correct
31 Execution timed out 4059 ms 95472 KB Time limit exceeded
32 Halted 0 ms 0 KB -