#include <bits/stdc++.h>
#define debug(x) [&] { auto _x = x; cerr << __LINE__ << ": " << #x << " = " << _x << endl; }()
using namespace std;
using ll = long long;
using pint = pair<int, int>;
#define all(x) x.begin(), x.end()
const int MAX = 1e6;
const ll INF = 1e18;
struct Val {
ll dist = INF;
int x, y;
bool operator<(const Val &o) const { return dist < o.dist; }
};
struct Node {
int l, r;
Val val;
bool lazy = false;
Node *lc, *rc;
Node(int l, int r, const vector<int> &arr) : l(l), r(r) {
if (l < r) {
int m = l + ((r - l) >> 1);
lc = new Node{l, m, arr};
rc = new Node{m + 1, r, arr};
}
this->l = arr[l], this->r = arr[r];
}
void clean() {
if (lazy) {
val.dist = INF;
if (l < r) lc->lazy = rc->lazy = lazy;
lazy = false;
}
}
Val query(int ql, int qr) {
if (ql > r or qr < l) return {};
clean();
if (l >= ql and r <= qr) return val;
return min(lc->query(ql, qr), rc->query(ql, qr));
}
void update(int i, const Val &v) {
clean();
if (i < l or i > r) return;
if (l == r) {
val = v;
return;
}
lc->update(i, v);
rc->update(i, v);
val = min(lc->val, rc->val);
}
void clear(int ul, int ur) {
clean();
if (ul > r or ur < l) return;
if (l >= ul and r <= ur) {
lazy = true;
clean();
return;
}
lc->clear(ul, ur);
rc->clear(ul, ur);
val = min(lc->val, rc->val);
}
};
int X, Y, n;
vector<pint> s[MAX + 1], e[MAX + 1];
map<pint, pint> pre;
int main() {
cin >> X >> Y >> n;
vector<int> arr{{0}};
for (int i = 0; i < n; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
s[x1].emplace_back(y1, y2);
e[x2].emplace_back(y1, y2);
arr.emplace_back(y1 - 1), arr.emplace_back(y2 + 1);
}
sort(all(arr));
arr.erase(unique(all(arr)), arr.end());
Node *up = new Node{0, (int) arr.size() - 1, arr}, *down = new Node{0, (int) arr.size() - 1, arr};
up->update(0, {0, 0, 0}), down->update(0, {0, 0, 0});
map<int, int> blocks;
blocks[-MAX - 2] = -MAX - 2;
blocks[MAX + 2] = MAX + 2;
auto dp = [&] (int y) {
auto it = blocks.upper_bound(y);
auto a = up->query(prev(it)->second + 1, y), b = down->query(y, it->first - 1);
a.dist += y, b.dist -= y;
return min(a, b);
};
for (int x = 0; x <= X; ++x) {
vector<pint> points;
for (auto [l, r]: s[x]) points.emplace_back(l - 1, 0), points.emplace_back(r + 1, 0);
sort(all(points));
points.erase(unique(all(points)), points.end());
for (auto &[y, v]: points) {
auto a = dp(y);
pre[{x - 1, y}] = {a.x, a.y};
v = a.dist;
}
for (auto [y, v]: points) {
up->update(y, {v - y, x - 1, y});
down->update(y, {v + y, x - 1, y});
}
for (auto [l, r]: e[x - 1]) blocks.erase(l);
for (auto [l, r]: s[x]) {
up->clear(l, r);
down->clear(l, r);
blocks[l] = r;
}
}
auto a = dp(Y);
cout << a.dist + X << endl;
pre[{X, Y}] = {a.x, a.y};
vector<pint> coords{{X, Y}};
while (X or Y) {
tie(X, Y) = pre[{X, Y}];
coords.emplace_back(X, Y);
}
vector<pint> ans;
while (coords.size() >= 2) {
if (coords.end()[-2].first != coords.back().first) {
if (ans.empty() or ans.back().second) ans.emplace_back(coords.end()[-2].first - coords.back().first, 0);
else ans.back().first += coords.end()[-2].first - coords.back().first;
}
if (coords.end()[-2].second != coords.back().second) {
if (ans.empty() or ans.back().first) ans.emplace_back(0, coords.end()[-2].second - coords.back().second);
else ans.back().second += coords.end()[-2].second - coords.back().second;
}
coords.pop_back();
}
cout << ans.size() << endl;
for (auto [x, y]: ans) cout << x << " " << y << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
47196 KB |
Output is correct |
| 2 |
Correct |
24 ms |
47196 KB |
Output is correct |
| 3 |
Correct |
28 ms |
47356 KB |
Output is correct |
| 4 |
Correct |
39 ms |
47960 KB |
Output is correct |
| 5 |
Correct |
411 ms |
77704 KB |
Output is correct |
| 6 |
Correct |
166 ms |
62832 KB |
Output is correct |
| 7 |
Correct |
243 ms |
59568 KB |
Output is correct |
| 8 |
Correct |
366 ms |
66844 KB |
Output is correct |
| 9 |
Correct |
343 ms |
65732 KB |
Output is correct |
| 10 |
Correct |
383 ms |
66164 KB |
Output is correct |
