Submission #742737

#TimeUsernameProblemLanguageResultExecution timeMemory
742737finn__Walk (CEOI06_walk)C++17
90 / 100
130 ms45124 KiB
#include <bits/stdc++.h> using namespace std; constexpr size_t N = 100000, L = 1 << 20; struct rect { int64_t x[2], y[2], i; }; rect r[N]; int64_t tree[2 * L], d[N][2], g[N][2]; bool pre[N][2]; void update(int64_t x, int64_t i) { tree[x += L] = i; while (x >>= 1) tree[x] = tree[2 * x + 1] != -1 ? tree[2 * x + 1] : tree[2 * x]; } int64_t rightmost_set(int64_t j) { j += L; int64_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; } int64_t get_distance(int64_t i, bool i_type, int64_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)); } int64_t get_shortest_path(int64_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)); } int64_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); int64_t x, y; size_t n; cin >> x >> y >> n; vector<tuple<int64_t, int64_t, int64_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'; int64_t i = n; bool type = 0; vector<pair<int64_t, int64_t>> path; auto add_point = [&path](int64_t x, int64_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) { int64_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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...