#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 100001, L = 1 << 20;
struct rect
{
int32_t x[2], y[2], i;
};
rect r[N];
int32_t tree[2 * L], d[N][2], g[N][2];
bool pre[N][2];
void update(int32_t x, int32_t i)
{
tree[x += L] = i;
while (x >>= 1)
tree[x] = tree[2 * x + 1] != -1 ? tree[2 * x + 1] : tree[2 * x];
}
int32_t rightmost_set(int32_t j)
{
j += L;
int32_t u = -1, v = -1, i = L;
while (i <= j)
{
if (i & 1)
u = tree[i] != -1 ? tree[i] : u, ++i;
if (!(j & 1))
v = v == -1 ? tree[j] : v, --j;
i >>= 1;
j >>= 1;
}
return v != -1 ? v : u;
}
int32_t get_distance(int32_t i, bool i_type, int32_t j, bool j_type)
{
return abs(r[i].x[i_type] + (i_type ? 1 : -1) - r[j].x[j_type] - (j_type ? 1 : -1)) +
abs(r[i].y[i_type] + (i_type ? 1 : -1) - r[j].y[j_type] - (j_type ? 1 : -1));
}
int32_t get_shortest_path(int32_t i, bool type)
{
if (d[i][type])
return d[i][type];
if (g[i][type] == -1)
{
return d[i][type] = r[i].x[type] + (type ? 1 : -1) + abs(r[i].y[type] + (type ? 1 : -1));
}
int32_t const d1 = get_distance(i, type, g[i][type], 0) + get_shortest_path(g[i][type], 0),
d2 = get_distance(i, type, g[i][type], 1) + get_shortest_path(g[i][type], 1);
pre[i][type] = d2 < d1;
return d[i][type] = min(d1, d2);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int32_t x, y;
size_t n;
cin >> x >> y >> n;
vector<tuple<int32_t, int32_t, int32_t>> e;
for (size_t i = 0; i < n; ++i)
{
cin >> r[i].x[0] >> r[i].y[0] >> r[i].x[1] >> r[i].y[1];
e.emplace_back(r[i].y[0], 0, i);
e.emplace_back(r[i].y[0] - 1, 1, i);
e.emplace_back(r[i].y[1] + 1, 2, i);
e.emplace_back(r[i].y[1], 3, i);
}
r[n].x[0] = r[n].x[1] = x + 1, r[n].y[0] = r[n].y[1] = y + 1, r[n].i = n;
e.emplace_back(r[n].y[0] - 1, 1, n);
sort(e.begin(), e.end());
memset(tree, 255, sizeof tree);
for (auto const &[_y, type, i] : e)
if (!type)
update(r[i].x[1], i);
else if (type == 1)
g[i][0] = rightmost_set(r[i].x[0] - 1);
else if (type == 2)
g[i][1] = rightmost_set(r[i].x[0] - 1);
else
update(r[i].x[1], -1);
cout << get_shortest_path(n, 0) << '\n';
int32_t i = n;
bool type = 0;
vector<pair<int32_t, int32_t>> path;
auto add_point = [&path](int32_t x, int32_t y)
{
if (path.size() >= 2 && ((x == path.back().first && path.back().first == (++path.rbegin())->first) ||
(y == path.back().second && path.back().second == (++path.rbegin())->second)))
path.pop_back();
path.emplace_back(x, y);
};
while (g[i][type] != -1)
{
int32_t j = g[i][type];
bool next_type = pre[i][type];
add_point(r[i].x[type] + (type ? 1 : -1), r[i].y[type] + (type ? 1 : -1));
add_point(r[j].x[1] + 1, r[i].y[type] + (type ? 1 : -1));
if (!next_type)
add_point(r[j].x[1] + 1, r[j].y[0] - 1);
i = j;
type = next_type;
}
add_point(r[i].x[type] + (type ? 1 : -1), r[i].y[type] + (type ? 1 : -1));
add_point(0, r[i].y[type] + (type ? 1 : -1));
add_point(0, 0);
cout << path.size() - 1 << '\n';
for (auto it = path.rbegin() + 1; it != path.rend(); ++it)
cout << it->first - (it - 1)->first << ' ' << it->second - (it - 1)->second << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
8516 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8508 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8660 KB |
Output is correct |
| 5 |
Correct |
119 ms |
16576 KB |
Output is correct |
| 6 |
Correct |
45 ms |
11288 KB |
Output is correct |
| 7 |
Correct |
64 ms |
13020 KB |
Output is correct |
| 8 |
Correct |
134 ms |
17164 KB |
Output is correct |
| 9 |
Correct |
149 ms |
17736 KB |
Output is correct |
| 10 |
Correct |
126 ms |
17908 KB |
Output is correct |
