Submission #792288

#	Time	Username	Problem	Language	Result	Execution time	Memory
792288		skittles1412	Sky Walking (IOI19_walk)	C++17	33 / 100	469 ms	96660 KiB

walk

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

template <typename Cb>
struct CmpByKey {
    Cb cb;

    CmpByKey(const Cb& cb) : cb(cb) {}

    template <typename T>
    bool operator()(const T& a, const T& b) const {
        return cb(a) < cb(b);
    }
};

template <typename T>
struct Comp {
    map<T, int> mp;

    int operator()(const T& t) {
        auto [it, inserted] = mp.emplace(t, -1);
        if (inserted) {
            it->second = sz(mp) - 1;
        }
        return it->second;
    }
};

template <typename T, typename Cmp = less<T>>
vector<T> sorted(vector<T> arr, Cmp cmp = Cmp()) {
    sort(begin(arr), end(arr), cmp);
    return arr;
}

template <typename S>
long dijkstra(const vector<tuple<S, S, long>>& edges, S src, S dest) {
    dbg("A");
    int n = 2 * sz(edges) + 10;

    Comp<S> comp;
    vector<pair<int, long>> graph[n];

    for (auto& [u, v, w] : edges) {
        int cu = comp(u), cv = comp(v);
        graph[cu].emplace_back(cv, w);
        graph[cv].emplace_back(cu, w);
    }

    long dist[n];
    memset(dist, 0x3f, sizeof(dist));

    min_pq<pair<long, int>> pq;
    auto push = [&](int u, long d) -> void {
        if (d >= dist[u]) {
            return;
        }
        dist[u] = d;
        pq.emplace(d, u);
    };

    int c_src = comp(src), c_dest = comp(dest);

    push(c_src, 0);

    while (sz(pq)) {
        auto [d, u] = pq.top();
        pq.pop();

        if (u == c_dest) {
            return d;
        }
        if (d != dist[u]) {
            continue;
        }

        for (auto& [v, w] : graph[u]) {
            push(v, d + w);
        }
    }

    return -1;
}

namespace s1 {

long solve(vector<pair<int, int>> arr,
           vector<array<int, 3>> walk,
           int src,
           int dest) {
    map<int, vector<pair<int, int>>> evts;
    for (auto& [x, h] : arr) {
        evts[-h].emplace_back(x, -1);
    }
    for (auto& [ql, qr, h] : walk) {
        evts[-h].emplace_back(ql, qr);
    }

    vector<array<int, 3>> d_walk;
    {
        set<int> pos;
        for (auto& [nh, ev] : evts) {
            int h = -nh;

            for (auto& [x, ty] : ev) {
                if (ty == -1) {
                    dbg(h, x);
                    pos.insert(x);
                }
            }

            for (auto& [ql, qr] : ev) {
                if (qr == -1) {
                    continue;
                }
                dbg(h, ql, qr);

                auto it = pos.lower_bound(ql);
                while (true) {
                    int cl = *it;
                    ++it;
                    int cr = *it;
                    d_walk.push_back({cl, cr, h});

                    dbg("A", *it, qr);
                    assert(*it <= qr);
                    if (*it == qr) {
                        break;
                    }
                }
            }
        }
    }

    for (auto& [ql, qr, h] : d_walk) {
        dbg(ql, qr, h);
    }

    using S = pair<int, int>;

    S s_src {src, 0}, s_dest {dest, 0};
    vector<S> states {s_src, s_dest};
    for (auto& [ql, qr, h] : d_walk) {
        states.emplace_back(ql, h);
        states.emplace_back(qr, h);
    }

    sort(begin(states), end(states));
    states.erase(unique(begin(states), end(states)), states.end());

    map<int, vector<int>> buildings;
    for (auto& [x, y] : states) {
        buildings[x].push_back(y);
    }

    vector<tuple<S, S, long>> edges;

    for (auto& [x, ys] : buildings) {
        sort(begin(ys), end(ys));
        for (int i = 0; i + 1 < sz(ys); i++) {
            edges.emplace_back(S(x, ys[i]), S(x, ys[i + 1]), ys[i + 1] - ys[i]);
        }
    }

    for (auto& [ql, qr, h] : d_walk) {
        edges.emplace_back(S(ql, h), S(qr, h), qr - ql);
    }

    for (auto& [u, v, w] : edges) {
        dbg(u, v, w);
    }

    return dijkstra(edges, s_src, s_dest);
}

}  // namespace s1

namespace s2 {

template <typename Cb>
void add_edges(vector<array<int, 4>> arr, const Cb& cb) {
    for (auto& [_ql, qr, _i, _] : arr) {
        // [] -> [)
        qr++;
    }

    int n = sz(arr);

    map<pair<int, int>, int> mp;

    auto split = [&](int ind) -> void {
        auto it = mp.lower_bound({ind + 1, -1});
        if (it == mp.begin()) {
            return;
        }
        --it;
        auto [cql, cqr] = it->first;

        if (cql < ind && ind < cqr) {
            int cv = it->second;
            mp.erase(it);
            mp[{cql, ind}] = cv;
            mp[{ind, cqr}] = cv;
        }
    };

    for (auto& [ql, qr, qi, _] : arr) {
        split(ql);
        split(qr);

        for (auto it = mp.lower_bound({ql, -1}); it != mp.end();
             it = mp.erase(it)) {
            auto [cql, cqr] = it->first;
            if (qr <= cql) {
                break;
            }

            assert(ql <= cql && cqr <= qr);
            cb(qi, it->second);
        }

        mp[{ql, qr}] = qi;
    }
}

long solve(vector<pair<int, int>> arr,
           vector<array<int, 3>> walk,
           int src,
           int dest) {
    int c_src = sz(walk), c_dest = sz(walk) + 1;
    walk.push_back({src, src, 0});
    walk.push_back({dest, dest, 0});

    vector<tuple<int, int, long>> edges;

    // auto inter = [&](int l1, int r1, int l2, int r2) -> bool {
    //     if (l1 > l2) {
    //         swap(l1, l2);
    //         swap(r1, r2);
    //     }
    //     return l2 <= r1;
    // };
    // for (int i = 0; i < sz(walk); i++) {
    //     for (int j = i + 1; j < sz(walk); j++) {
    //         auto& [l1, r1, h1] = walk[i];
    //         auto& [l2, r2, h2] = walk[j];

    //         if (inter(l1, r1, l2, r2)) {
    //             dbg(i, j);
    //             edges.emplace_back(i, j, abs(h1 - h2));
    //         }
    //     }
    // }

    vector<array<int, 4>> n_walk;
    for (int i = 0; i < sz(walk); i++) {
        auto& [ql, qr, qh] = walk[i];
        n_walk.push_back({ql, qr, i, qh});
    }

    auto cb_edge = [&](int u, int v) -> void {
        dbg(u, v);
        edges.emplace_back(u, v, abs(walk[u][2] - walk[v][2]));
    };

    add_edges(
        sorted(n_walk, CmpByKey([&](const auto& a) -> int { return a[3]; })),
        cb_edge);
    add_edges(
        sorted(n_walk, CmpByKey([&](const auto& a) -> int { return -a[3]; })),
        cb_edge);

    long ans = dijkstra(edges, c_src, c_dest);
    if (ans == -1) {
        return ans;
    } else {
        return ans + dest - src;
    }
}

}  // namespace s2

ll min_distance(vector<int> arr_x,
                vector<int> arr_h,
                vector<int> walk_l,
                vector<int> walk_r,
                vector<int> walk_y,
                int src,
                int dest) {
    int n = sz(arr_x), m = sz(walk_l);

    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = {arr_x[i], arr_h[i]};
    }

    vector<array<int, 3>> walk(m);
    for (int i = 0; i < m; i++) {
        walk[i] = {arr[walk_l[i]].first, arr[walk_r[i]].first, walk_y[i]};
    }

    src = arr[src].first;
    dest = arr[dest].first;

    return s2::solve(arr, walk, src, dest);
}

Compilation message (stderr)

walk.cpp: In function 'int64_t s1::solve(std::vector<std::pair<int, int> >, std::vector<std::array<int, 3> >, int, int)':
walk.cpp:167:16: warning: unused structured binding declaration [-Wunused-variable]
  167 |     for (auto& [ql, qr, h] : d_walk) {
      |                ^~~~~~~~~~~
walk.cpp:201:16: warning: unused structured binding declaration [-Wunused-variable]
  201 |     for (auto& [u, v, w] : edges) {
      |                ^~~~~~~~~
walk.cpp: In instantiation of 'void s2::add_edges(std::vector<std::array<int, 4> >, const Cb&) [with Cb = s2::solve(std::vector<std::pair<int, int> >, std::vector<std::array<int, 3> >, int, int)::<lambda(int, int)>]':
walk.cpp:300:16:   required from here
walk.cpp:219:9: warning: unused variable 'n' [-Wunused-variable]
  219 |     int n = sz(arr);
      |         ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43