Submission #792338

#	Time	Username	Problem	Language	Result	Execution time	Memory
792338		skittles1412	Sky Walking (IOI19_walk)	C++17	100 / 100	3371 ms	643344 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;

    vector<S> a_s {src, dest};
    for (auto& [u, v, _w] : edges) {
        a_s.push_back(u);
        a_s.push_back(v);
    }
    sort(begin(a_s), end(a_s));
    a_s.erase(unique(begin(a_s), end(a_s)), a_s.end());

    auto comp = [&](S s) -> int {
        return int(lower_bound(begin(a_s), end(a_s), s) - a_s.begin());
    };

    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) {
    clock_t c_start = clock();
    map<int, int> x_to_h;
    for (auto& [x, h] : arr) {
        x_to_h[x] = h;
    }
    int src_h = x_to_h[src], dest_h = x_to_h[dest];
    assert(src_h && dest_h);

    int c_src = sz(walk), c_dest = sz(walk) + 1;
    walk.push_back({src, src, 0});
    walk.push_back({dest, dest, 0});

    using S = pair<int, int>;

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

    auto add_edge = [&](S s1, S s2) -> void {
        if (s1 > s2) {
            swap(s1, s2);
        }
        auto& [x1, y1] = s1;
        auto& [x2, y2] = s2;
        assert(x1 == x2 || y1 == y2);
        // dbg(s1, s2);
        edges.emplace_back(s1, s2, abs(x1 - x2) + abs(y1 - y2));
    };

    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});
    }

    vector<S> w_segs[sz(walk)];

    vector<array<int, 5>> queries;

    auto inter = [&](int l1, int r1, int l2, int r2) -> bool {
        if (l1 > l2) {
            swap(l1, l2);
            swap(r1, r2);
        }
        return l2 <= r1;
    };

    auto go = [&](int u, int v, int x) -> void {
        int h1 = walk[u][2], h2 = walk[v][2];
        w_segs[u].emplace_back(x, h1);
        w_segs[v].emplace_back(x, h2);

        add_edge(S {x, h1}, S {x, h2});
    };
    auto go_query = [&](int cql, int cqr, int mh, int u, int v) -> void {
        set<int> pos;
        for (auto& [x, h] : arr) {
            if (mh <= h) {
                pos.insert(x);
            }
        }
        auto go_c = [&](int x) -> void {
            if (cql <= x && x <= cqr) {
                // dbg(u, v, x);
                go(u, v, x);
            }
        };
        auto f_nearest = [&](int base) -> void {
            auto it = pos.lower_bound(base);
            if (it != pos.end()) {
                go_c(*it);
            }
            if (it != pos.begin()) {
                go_c(*(--it));
            }
        };
        f_nearest(cql);
        f_nearest(cqr);
        f_nearest(src);
        f_nearest(dest);
    };
    auto cb_edge = [&](int u, int v) -> void {
        auto [l1, r1, h1] = walk[u];
        auto [l2, r2, h2] = walk[v];
        if (!inter(l1, r1, l2, r2)) {
            return;
        }

        int cql = max(l1, l2), cqr = min(r1, r2);
        queries.push_back({cql, cqr, max(h1, h2), u, v});
    };

    for (int i = 0; i < sz(walk); i++) {
        cb_edge(i, c_src);
        cb_edge(i, c_dest);
    }

    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);

    map<int, vector<pair<bool, int>>> mp;
    for (auto& [x, h] : arr) {
        mp[-h].emplace_back(true, x);
    }
    for (int i = 0; i < sz(queries); i++) {
        mp[-queries[i][2]].emplace_back(false, i);
    }

    set<int> pos;

    dbg(double(clock() - c_start) / CLOCKS_PER_SEC);
    for (auto& [nh, e] : mp) {
        for (auto& [ty, x] : e) {
            if (ty) {
                pos.insert(x);
            }
        }

        for (auto& [ty, qi] : e) {
            if (ty) {
                continue;
            }
            auto& [cql, cqr, _h, u, v] = queries[qi];

            vector<int> ccache;
            auto go_c = [&](int x) -> void {
                if (cql <= x && x <= cqr) {
                    ccache.push_back(x);
                }
            };
            auto f_nearest = [&](int base) -> void {
                auto it = pos.lower_bound(base);
                if (it != pos.end()) {
                    go_c(*it);
                }
                if (it != pos.begin()) {
                    go_c(*(--it));
                }
            };

            f_nearest(cql);
            f_nearest(cqr);
            f_nearest(src);
            f_nearest(dest);

            sort(begin(ccache), end(ccache));
            ccache.erase(unique(begin(ccache), end(ccache)), ccache.end());
            for (auto& a : ccache) {
                go(u, v, a);
            }
        }
    }

    dbg(double(clock() - c_start) / CLOCKS_PER_SEC);
    for (auto& a : w_segs) {
        sort(begin(a), end(a));
        a.erase(unique(begin(a), end(a)), a.end());

        for (int i = 0; i + 1 < sz(a); i++) {
            add_edge(a[i], a[i + 1]);
        }
    }

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

    dbg(double(clock() - c_start) / CLOCKS_PER_SEC);
    long ans = dijkstra(edges, S {src, 0}, S {dest, 0});

    dbg(double(clock() - c_start) / CLOCKS_PER_SEC);
    return ans;
}

}  // 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_x[walk_l[i]], arr_x[walk_r[i]], walk_y[i]};
    }

    src = arr_x[src];
    dest = arr_x[dest];

    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:178:16: warning: unused structured binding declaration [-Wunused-variable]
  178 |     for (auto& [ql, qr, h] : d_walk) {
      |                ^~~~~~~~~~~
walk.cpp:212:16: warning: unused structured binding declaration [-Wunused-variable]
  212 |     for (auto& [u, v, w] : edges) {
      |                ^~~~~~~~~
walk.cpp: In function 'int64_t s2::solve(std::vector<std::pair<int, int> >, std::vector<std::array<int, 3> >, int, int)':
walk.cpp:273:13: warning: unused variable 'c_start' [-Wunused-variable]
  273 |     clock_t c_start = clock();
      |             ^~~~~~~
walk.cpp:325:10: warning: variable 'go_query' set but not used [-Wunused-but-set-variable]
  325 |     auto go_query = [&](int cql, int cqr, int mh, int u, int v) -> void {
      |          ^~~~~~~~
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:370:16:   required from here
walk.cpp:230:9: warning: unused variable 'n' [-Wunused-variable]
  230 |     int n = sz(arr);
      |         ^

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