Submission #742739

#	Time	Username	Problem	Language	Result	Execution time	Memory
742739		finn__	Walk (CEOI06_walk)	C++17	90 / 100	136 ms	48224 KiB

walk

#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] != -1)
        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);

    memset(d, 255, sizeof d);
    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';
}

• Subtask 1: 90 / 100