Submission #714941

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
714941	2023-03-25T14:33:33 Z	mbfibat	Walk (CEOI06_walk)	C++17	100 / 100	160 ms	11700 KB

walk

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

int seg[8000011], lazy[8000011];

void diffuse(int node, int l, int r) {
	if (lazy[node]) {
		seg[node] = lazy[node];
		if (l != r) {
			lazy[node * 2] = lazy[node];
			lazy[node * 2 + 1] = lazy[node];
		}
		lazy[node] = 0;
	}
}

void update(int node, int l, int r, int L, int R, int val) {
	diffuse(node, l, r);
	if (r < L || R < l) return;
	if (L <= l && r <= R) {
		lazy[node] = val;
		diffuse(node, l, r);
		return;
	}

	int mi = (l + r) / 2;
	update(node * 2, l, mi, L, R, val);
	update(node * 2 + 1, mi + 1, r, L, R, val);
	seg[node] = max(seg[node * 2], seg[node * 2 + 1]); // Not needed because only query point lmao
}

int query(int node, int l, int r, int p) {
	diffuse(node, l, r);
	if (p < l || r < p) return 0;
	if (p == l && l == r)
		return seg[node];

	int mi = (l + r) / 2;
	int lhs = query(node * 2, l, mi, p);
	int rhs = query(node * 2 + 1, mi + 1, r, p);
	return max(lhs, rhs);
}

struct Point {
	int x, y, id, t;
	Point(){}
	Point(int x, int y) : x(x), y(y) {}
	Point(int x, int y, int id, int t) : x(x), y(y), id(id), t(t) {}

	bool operator<(Point& other) {
		return x < other.x || (x == other.x && id > other.id);
	}
};

struct Event {
	int x, y1, y2, v;
	Event(){}
	Event(int x, int y1, int y2, int v) : x(x), y1(y1), y2(y2), v(v) {}

	bool operator<(Event& other) {
		return x < other.x;
	}
};

int X, Y;
int n;

ii mat[2][1000001];
int val[2][1000001];

int nxt_point[1000001];
int pos_in_p[2][1000001];

int main(int argc, char** argv) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> X >> Y >> n;
	
	vector<Point> p;
	vector<Event> e;
	p.emplace_back(X, Y, 0, 0);

	for (int i = 1; i <= n; i++) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		p.emplace_back(x2 + 1, y1 - 1, i, 0);
		p.emplace_back(x2 + 1, y2 + 1, i, 1);
		e.emplace_back(x1, y1, y2, i);

		mat[0][i] = ii(x2 + 1, y1 - 1);
		mat[1][i] = ii(x2 + 1, y2 + 1);
	}

	sort(p.begin(), p.end());
	sort(e.begin(), e.end());

	for (int i = 0; i < p.size(); i++)
		pos_in_p[p[i].t][p[i].id] = i;

	int pos_p = 0, pos_e = 0;
	for (int x = 1; x <= 1000000; x++) {
		while (pos_e < e.size() && e[pos_e].x == x) {
//			cerr << '!' << e[pos_e].y1 << ' ' << e[pos_e].y2 << ' ' << e[pos_e].v << '\n';
			update(1, 0, 2000000, e[pos_e].y1 + 1000000, e[pos_e].y2 + 1000000, e[pos_e].v);
			++pos_e;
		}
		while (pos_p < p.size() && p[pos_p].x == x) {
			int nxt = query(1, 0, 2000000, p[pos_p].y + 1000000);
//			cerr << '!' << pos_p << ' ' << p[pos_p].x << ' ' << p[pos_p].y << ' ' << nxt << '\n';
			if (!nxt) {
				val[p[pos_p].t][p[pos_p].id] = abs(p[pos_p].y);
				nxt_point[pos_p] = -1;
			}	
			else {
				int d = val[0][nxt] + abs(mat[0][nxt].second - p[pos_p].y);
				int u = val[1][nxt] + abs(mat[1][nxt].second - p[pos_p].y);
//				cerr << p[pos_p].t << ' ' << p[pos_p].id << ' ' << u << ' ' << d << '\n';
				val[p[pos_p].t][p[pos_p].id] = min(u, d);
				if (d < u)
					nxt_point[pos_p] = pos_in_p[0][nxt];
				else
					nxt_point[pos_p] = pos_in_p[1][nxt]; 
			}
			++pos_p;
		}
	}
	
	int ans = val[0][0];
	vector<ii> path;

	for (int i = 0; i < p.size(); i++) {
		if (p[i].x == X && p[i].y == Y) {
			// find path
			int cur = i;
			while (1) {
				int nxt = nxt_point[cur];
//				cerr << '?' << p[cur].x << ' ' << p[cur].y << '\n';
//				cerr << cur << ' ' << nxt << '\n';
				if (nxt == -1) {
					if (p[cur].x) path.emplace_back(p[cur].x, 0);
					if (p[cur].y) path.emplace_back(0, p[cur].y);
					break;
				}	
				if (p[cur].x - p[nxt].x) path.emplace_back(p[cur].x - p[nxt].x, 0);
				if (p[cur].y - p[nxt].y) path.emplace_back(0, p[cur].y - p[nxt].y);
				cur = nxt;
			}
			break;
		}
	}
	reverse(path.begin(), path.end());

	cout << ans + X << '\n';
	cout << path.size() << '\n';
	for (auto& [dx, dy] : path)
		cout << dx << ' ' << dy << '\n';
}

Compilation message

walk.cpp: In function 'int main(int, char**)':
walk.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~
walk.cpp:105:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   while (pos_e < e.size() && e[pos_e].x == x) {
      |          ~~~~~~^~~~~~~~~~
walk.cpp:110:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   while (pos_p < p.size() && p[pos_p].x == x) {
      |          ~~~~~~^~~~~~~~~~
walk.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |  for (int i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	2 ms	468 KB	Output is correct
3	Correct	3 ms	1476 KB	Output is correct
4	Correct	4 ms	1236 KB	Output is correct
5	Correct	121 ms	11360 KB	Output is correct
6	Correct	45 ms	5016 KB	Output is correct
7	Correct	75 ms	6312 KB	Output is correct
8	Correct	160 ms	11700 KB	Output is correct
9	Correct	149 ms	11640 KB	Output is correct
10	Correct	151 ms	11576 KB	Output is correct