Submission #726789

#	Time	Username	Problem	Language	Result	Execution time	Memory
726789		vjudge1	Walk (CEOI06_walk)	C++17	100 / 100	162 ms	13524 KiB

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 (stderr)

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 / 100