#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 100000, 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], 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)
{
pre[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';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
8532 KB |
Unexpected end of file - token expected |
| 2 |
Incorrect |
4 ms |
8532 KB |
Unexpected end of file - token expected |
| 3 |
Incorrect |
4 ms |
8532 KB |
Unexpected end of file - token expected |
| 4 |
Incorrect |
5 ms |
8660 KB |
Unexpected end of file - token expected |
| 5 |
Incorrect |
93 ms |
18648 KB |
Unexpected end of file - token expected |
| 6 |
Incorrect |
33 ms |
11992 KB |
Unexpected end of file - token expected |
| 7 |
Incorrect |
64 ms |
14328 KB |
Unexpected end of file - token expected |
| 8 |
Incorrect |
110 ms |
18012 KB |
Found length -1, official output says 16349. |
| 9 |
Incorrect |
123 ms |
19540 KB |
Unexpected end of file - token expected |
| 10 |
Incorrect |
114 ms |
19760 KB |
Unexpected end of file - token expected |
