Submission #369517

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
369517	2021-02-21T19:29:41 Z	dolphingarlic	Walk (CEOI06_walk)	C++14	100 / 100	148 ms	17884 KB

walk

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

const ll INF = 1e13;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	ll x, y;
	cin >> x >> y;
	int n;
	cin >> n;
	vector<tuple<ll, ll, ll, ll>> rects;
	for (int i = 0; i < n; ++i) {
		ll x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x2 < x) rects.emplace_back(x1, y1, x2, y2);
	}
	rects.emplace_back(-1, -INF, -1, -1);
	rects.emplace_back(-1, 1, -1, INF);

	map<ll, pair<ll, ll>> cur;  // cur[y] = {x, dist}
	map<pair<ll, ll>, pair<ll, ll>> parent;
	cur[y] = {x, 0};
	sort(rects.begin(), rects.end(),
		 [](auto t1, auto t2) { return get<2>(t1) > get<2>(t2); });
	for (auto t : rects) {
		ll x1, y1, x2, y2;
		tie(x1, y1, x2, y2) = t;
		if (x1 > x2) swap(x1, x2);
		if (y1 > y2) swap(y1, y2);
		ll y1d = INF, y2d = INF;
		pair<ll, ll> y1p, y2p;
		while (cur.lower_bound(y1) != cur.end()) {
			ll cx, cy, cd;
			auto aux = tie(cx, cd);
			tie(cy, aux) = *cur.lower_bound(y1);
			if (cy > y2) break;
			cur.erase(cur.lower_bound(y1));
			ll candY1d = cd + cy - (y1 - 1);
			ll candY2d = cd + (y2 + 1) - cy;
			if (candY1d < y1d) {
				y1d = candY1d;
				y1p = {cx, cy};
			}
			if (candY2d < y2d) {
				y2d = candY2d;
				y2p = {cx, cy};
			}
		}
		if (cur.count(y1 - 1) == 0 || cur[y1 - 1].second > y1d) {
			cur[y1 - 1] = {x2 + 1, y1d};
			parent[{x2 + 1, y1 - 1}] = y1p;
		}
		if (cur.count(y2 + 1) == 0 || cur[y2 + 1].second > y2d) {
			cur[y2 + 1] = {x2 + 1, y2d};
			parent[{x2 + 1, y2 + 1}] = y2p;
		}
	}

	cout << cur[0].second + x << endl;
	vector<pair<ll, ll>> ans;
	pair<ll, ll> p;
	while (p != make_pair(x, y)) {
		ans.emplace_back(0, parent[p].second - p.second);
		ans.emplace_back(parent[p].first - p.first, 0);
		p = parent[p];
	}
	if (ans.back() == make_pair(0LL, 0LL)) ans.pop_back();
	cout << ans.size() << endl;
	for (auto p : ans) cout << p.first << ' ' << p.second << '\n';
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	119 ms	16860 KB	Output is correct
6	Correct	45 ms	6376 KB	Output is correct
7	Correct	82 ms	9856 KB	Output is correct
8	Correct	148 ms	14172 KB	Output is correct
9	Correct	128 ms	17884 KB	Output is correct
10	Correct	135 ms	17756 KB	Output is correct