oj.uz

Submission #792334

# Submission time Handle Problem Language Result Execution time Memory
792334 2023-07-25T01:22:22 Z skittles1412 Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 553648 KB 
#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) {
    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 = [&](const S& s1, const S& s2) -> void {
        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;

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

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

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

    return dijkstra(edges, S {src, 0}, S {dest, 0});
}

}  // 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

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 function 'int64_t s2::solve(std::vector<std::pair<int, int> >, std::vector<std::array<int, 3> >, int, int)':
walk.cpp:310:10: warning: variable 'go_query' set but not used [-Wunused-but-set-variable]
  310 |     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:355:16:   required from here
walk.cpp:219:9: warning: unused variable 'n' [-Wunused-variable]
  219 |     int n = sz(arr);
      |         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 468 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2192 ms 372792 KB Output is correct
4 Correct 2480 ms 373728 KB Output is correct
5 Correct 1470 ms 280512 KB Output is correct
6 Correct 1348 ms 254936 KB Output is correct
7 Correct 1487 ms 280328 KB Output is correct
8 Correct 2850 ms 405276 KB Output is correct
9 Correct 2129 ms 349600 KB Output is correct
10 Correct 2747 ms 412196 KB Output is correct
11 Correct 1569 ms 280652 KB Output is correct
12 Correct 954 ms 142468 KB Output is correct
13 Correct 2696 ms 415504 KB Output is correct
14 Correct 771 ms 172904 KB Output is correct
15 Correct 782 ms 154968 KB Output is correct
16 Correct 842 ms 159004 KB Output is correct
17 Correct 906 ms 151024 KB Output is correct
18 Correct 1120 ms 357412 KB Output is correct
19 Correct 21 ms 7964 KB Output is correct
20 Correct 292 ms 77932 KB Output is correct
21 Correct 1051 ms 163468 KB Output is correct
22 Correct 778 ms 135124 KB Output is correct
23 Correct 921 ms 223232 KB Output is correct
24 Correct 825 ms 147632 KB Output is correct
25 Correct 909 ms 149964 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 109572 KB Output is correct
2 Correct 3395 ms 503860 KB Output is correct
3 Correct 3918 ms 529152 KB Output is correct
4 Correct 3799 ms 542304 KB Output is correct
5 Execution timed out 4006 ms 553648 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 109572 KB Output is correct
2 Correct 3395 ms 503860 KB Output is correct
3 Correct 3918 ms 529152 KB Output is correct
4 Correct 3799 ms 542304 KB Output is correct
5 Execution timed out 4006 ms 553648 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2192 ms 372792 KB Output is correct
21 Correct 2480 ms 373728 KB Output is correct
22 Correct 1470 ms 280512 KB Output is correct
23 Correct 1348 ms 254936 KB Output is correct
24 Correct 1487 ms 280328 KB Output is correct
25 Correct 2850 ms 405276 KB Output is correct
26 Correct 2129 ms 349600 KB Output is correct
27 Correct 2747 ms 412196 KB Output is correct
28 Correct 1569 ms 280652 KB Output is correct
29 Correct 954 ms 142468 KB Output is correct
30 Correct 2696 ms 415504 KB Output is correct
31 Correct 771 ms 172904 KB Output is correct
32 Correct 782 ms 154968 KB Output is correct
33 Correct 842 ms 159004 KB Output is correct
34 Correct 906 ms 151024 KB Output is correct
35 Correct 1120 ms 357412 KB Output is correct
36 Correct 21 ms 7964 KB Output is correct
37 Correct 292 ms 77932 KB Output is correct
38 Correct 1051 ms 163468 KB Output is correct
39 Correct 778 ms 135124 KB Output is correct
40 Correct 921 ms 223232 KB Output is correct
41 Correct 825 ms 147632 KB Output is correct
42 Correct 909 ms 149964 KB Output is correct
43 Correct 459 ms 109572 KB Output is correct
44 Correct 3395 ms 503860 KB Output is correct
45 Correct 3918 ms 529152 KB Output is correct
46 Correct 3799 ms 542304 KB Output is correct
47 Execution timed out 4006 ms 553648 KB Time limit exceeded
48 Halted 0 ms 0 KB -