#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++) {
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1236 KB |
Output is correct |
| 5 |
Correct |
146 ms |
13316 KB |
Output is correct |
| 6 |
Correct |
43 ms |
5604 KB |
Output is correct |
| 7 |
Correct |
77 ms |
7284 KB |
Output is correct |
| 8 |
Correct |
162 ms |
13524 KB |
Output is correct |
| 9 |
Correct |
138 ms |
13212 KB |
Output is correct |
| 10 |
Correct |
149 ms |
13364 KB |
Output is correct |
