Submission #792339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792339	2023-07-25T01:37:26 Z	skittles1412	Sky Walking (IOI19_walk)	C++17	100 / 100	3470 ms	792432 KB

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;
using u64 = uint64_t;

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

struct H {
    u64 x = 0;

    H& operator()(u64 y) {
        x += 0x18961568715 + y;
        x *= 0x82576789;
        x ^= x >> 19;
        x ^= x << 31;
        x ^= x >> 25;
        return *this;
    }

    template <typename A, typename B>
    H& operator()(const pair<A, B>& y) {
        return (*this)(y.first)(y.second);
    }
};

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

    __gnu_pbds::gp_hash_table<u64, __gnu_pbds::null_type> ht;

    edges.erase(remove_if(begin(edges), end(edges), [&](const tuple<S, S, long>& e) -> bool {
        auto& [a, b, c] = e;
        u64 key = H{}(a)(b)(c).x;
        return !ht.insert(key).second;
    }), edges.end());
    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

walk.cpp: In function 'int64_t s1::solve(std::vector<std::pair<int, int> >, std::vector<std::array<int, 3> >, int, int)':
walk.cpp:197:16: warning: unused structured binding declaration [-Wunused-variable]
  197 |     for (auto& [ql, qr, h] : d_walk) {
      |                ^~~~~~~~~~~
walk.cpp:231:16: warning: unused structured binding declaration [-Wunused-variable]
  231 |     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:292:13: warning: unused variable 'c_start' [-Wunused-variable]
  292 |     clock_t c_start = clock();
      |             ^~~~~~~
walk.cpp:344:10: warning: variable 'go_query' set but not used [-Wunused-but-set-variable]
  344 |     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:389:16:   required from here
walk.cpp:249:9: warning: unused variable 'n' [-Wunused-variable]
  249 |     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	1 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	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	280 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	212 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	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1503 ms	337116 KB	Output is correct
4	Correct	1721 ms	327884 KB	Output is correct
5	Correct	1189 ms	238692 KB	Output is correct
6	Correct	1024 ms	213920 KB	Output is correct
7	Correct	1161 ms	238844 KB	Output is correct
8	Correct	1621 ms	351944 KB	Output is correct
9	Correct	1473 ms	271520 KB	Output is correct
10	Correct	1870 ms	364520 KB	Output is correct
11	Correct	1100 ms	210112 KB	Output is correct
12	Correct	674 ms	91360 KB	Output is correct
13	Correct	1824 ms	361168 KB	Output is correct
14	Correct	547 ms	90472 KB	Output is correct
15	Correct	539 ms	83820 KB	Output is correct
16	Correct	523 ms	86896 KB	Output is correct
17	Correct	534 ms	83944 KB	Output is correct
18	Correct	616 ms	156640 KB	Output is correct
19	Correct	17 ms	4712 KB	Output is correct
20	Correct	207 ms	43036 KB	Output is correct
21	Correct	531 ms	84748 KB	Output is correct
22	Correct	509 ms	77004 KB	Output is correct
23	Correct	568 ms	121244 KB	Output is correct
24	Correct	505 ms	81696 KB	Output is correct
25	Correct	501 ms	83044 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	294 ms	58736 KB	Output is correct
2	Correct	1828 ms	436248 KB	Output is correct
3	Correct	2073 ms	459656 KB	Output is correct
4	Correct	2241 ms	471684 KB	Output is correct
5	Correct	2461 ms	489140 KB	Output is correct
6	Correct	2092 ms	438452 KB	Output is correct
7	Correct	965 ms	217872 KB	Output is correct
8	Correct	571 ms	81176 KB	Output is correct
9	Correct	2033 ms	414780 KB	Output is correct
10	Correct	659 ms	144860 KB	Output is correct
11	Correct	32 ms	6972 KB	Output is correct

Subtask #4

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	294 ms	58736 KB	Output is correct
2	Correct	1828 ms	436248 KB	Output is correct
3	Correct	2073 ms	459656 KB	Output is correct
4	Correct	2241 ms	471684 KB	Output is correct
5	Correct	2461 ms	489140 KB	Output is correct
6	Correct	2092 ms	438452 KB	Output is correct
7	Correct	965 ms	217872 KB	Output is correct
8	Correct	571 ms	81176 KB	Output is correct
9	Correct	2033 ms	414780 KB	Output is correct
10	Correct	659 ms	144860 KB	Output is correct
11	Correct	32 ms	6972 KB	Output is correct
12	Correct	2049 ms	459236 KB	Output is correct
13	Correct	2152 ms	481324 KB	Output is correct
14	Correct	2456 ms	499064 KB	Output is correct
15	Correct	1454 ms	328416 KB	Output is correct
16	Correct	1716 ms	370468 KB	Output is correct
17	Correct	2044 ms	427216 KB	Output is correct
18	Correct	1579 ms	328400 KB	Output is correct
19	Correct	1707 ms	370024 KB	Output is correct
20	Correct	1164 ms	251328 KB	Output is correct
21	Correct	128 ms	27488 KB	Output is correct
22	Correct	1514 ms	370708 KB	Output is correct
23	Correct	1427 ms	334436 KB	Output is correct
24	Correct	829 ms	176228 KB	Output is correct
25	Correct	1260 ms	274492 KB	Output is correct
26	Correct	486 ms	87220 KB	Output is correct
27	Correct	2482 ms	497452 KB	Output is correct
28	Correct	2188 ms	483228 KB	Output is correct
29	Correct	2193 ms	453676 KB	Output is correct
30	Correct	1032 ms	226996 KB	Output is correct
31	Correct	2029 ms	424568 KB	Output is correct
32	Correct	589 ms	121056 KB	Output is correct
33	Correct	557 ms	111888 KB	Output is correct
34	Correct	568 ms	130780 KB	Output is correct
35	Correct	847 ms	183744 KB	Output is correct
36	Correct	648 ms	117188 KB	Output is correct
37	Correct	530 ms	84820 KB	Output is correct
38	Correct	503 ms	76944 KB	Output is correct
39	Correct	548 ms	121276 KB	Output is correct
40	Correct	488 ms	81612 KB	Output is correct
41	Correct	504 ms	83024 KB	Output is correct

Subtask #5

43.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	1 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	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	280 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	468 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1503 ms	337116 KB	Output is correct
21	Correct	1721 ms	327884 KB	Output is correct
22	Correct	1189 ms	238692 KB	Output is correct
23	Correct	1024 ms	213920 KB	Output is correct
24	Correct	1161 ms	238844 KB	Output is correct
25	Correct	1621 ms	351944 KB	Output is correct
26	Correct	1473 ms	271520 KB	Output is correct
27	Correct	1870 ms	364520 KB	Output is correct
28	Correct	1100 ms	210112 KB	Output is correct
29	Correct	674 ms	91360 KB	Output is correct
30	Correct	1824 ms	361168 KB	Output is correct
31	Correct	547 ms	90472 KB	Output is correct
32	Correct	539 ms	83820 KB	Output is correct
33	Correct	523 ms	86896 KB	Output is correct
34	Correct	534 ms	83944 KB	Output is correct
35	Correct	616 ms	156640 KB	Output is correct
36	Correct	17 ms	4712 KB	Output is correct
37	Correct	207 ms	43036 KB	Output is correct
38	Correct	531 ms	84748 KB	Output is correct
39	Correct	509 ms	77004 KB	Output is correct
40	Correct	568 ms	121244 KB	Output is correct
41	Correct	505 ms	81696 KB	Output is correct
42	Correct	501 ms	83044 KB	Output is correct
43	Correct	294 ms	58736 KB	Output is correct
44	Correct	1828 ms	436248 KB	Output is correct
45	Correct	2073 ms	459656 KB	Output is correct
46	Correct	2241 ms	471684 KB	Output is correct
47	Correct	2461 ms	489140 KB	Output is correct
48	Correct	2092 ms	438452 KB	Output is correct
49	Correct	965 ms	217872 KB	Output is correct
50	Correct	571 ms	81176 KB	Output is correct
51	Correct	2033 ms	414780 KB	Output is correct
52	Correct	659 ms	144860 KB	Output is correct
53	Correct	32 ms	6972 KB	Output is correct
54	Correct	2049 ms	459236 KB	Output is correct
55	Correct	2152 ms	481324 KB	Output is correct
56	Correct	2456 ms	499064 KB	Output is correct
57	Correct	1454 ms	328416 KB	Output is correct
58	Correct	1716 ms	370468 KB	Output is correct
59	Correct	2044 ms	427216 KB	Output is correct
60	Correct	1579 ms	328400 KB	Output is correct
61	Correct	1707 ms	370024 KB	Output is correct
62	Correct	1164 ms	251328 KB	Output is correct
63	Correct	128 ms	27488 KB	Output is correct
64	Correct	1514 ms	370708 KB	Output is correct
65	Correct	1427 ms	334436 KB	Output is correct
66	Correct	829 ms	176228 KB	Output is correct
67	Correct	1260 ms	274492 KB	Output is correct
68	Correct	486 ms	87220 KB	Output is correct
69	Correct	2482 ms	497452 KB	Output is correct
70	Correct	2188 ms	483228 KB	Output is correct
71	Correct	2193 ms	453676 KB	Output is correct
72	Correct	1032 ms	226996 KB	Output is correct
73	Correct	2029 ms	424568 KB	Output is correct
74	Correct	589 ms	121056 KB	Output is correct
75	Correct	557 ms	111888 KB	Output is correct
76	Correct	568 ms	130780 KB	Output is correct
77	Correct	847 ms	183744 KB	Output is correct
78	Correct	648 ms	117188 KB	Output is correct
79	Correct	530 ms	84820 KB	Output is correct
80	Correct	503 ms	76944 KB	Output is correct
81	Correct	548 ms	121276 KB	Output is correct
82	Correct	488 ms	81612 KB	Output is correct
83	Correct	504 ms	83024 KB	Output is correct
84	Correct	252 ms	51112 KB	Output is correct
85	Correct	2169 ms	471496 KB	Output is correct
86	Correct	3070 ms	698984 KB	Output is correct
87	Correct	134 ms	34972 KB	Output is correct
88	Correct	221 ms	51056 KB	Output is correct
89	Correct	132 ms	35072 KB	Output is correct
90	Correct	89 ms	21812 KB	Output is correct
91	Correct	3 ms	1108 KB	Output is correct
92	Correct	66 ms	17992 KB	Output is correct
93	Correct	838 ms	189672 KB	Output is correct
94	Correct	141 ms	29608 KB	Output is correct
95	Correct	1604 ms	388660 KB	Output is correct
96	Correct	1426 ms	336200 KB	Output is correct
97	Correct	856 ms	177136 KB	Output is correct
98	Correct	1251 ms	274216 KB	Output is correct
99	Correct	3470 ms	792432 KB	Output is correct
100	Correct	2367 ms	465216 KB	Output is correct
101	Correct	2496 ms	513036 KB	Output is correct
102	Correct	1051 ms	235128 KB	Output is correct
103	Correct	620 ms	121840 KB	Output is correct
104	Correct	594 ms	113204 KB	Output is correct
105	Correct	612 ms	131076 KB	Output is correct
106	Correct	634 ms	118632 KB	Output is correct
107	Correct	587 ms	111260 KB	Output is correct
108	Correct	153 ms	40392 KB	Output is correct
109	Correct	1843 ms	371156 KB	Output is correct
110	Correct	2219 ms	484820 KB	Output is correct
111	Correct	2253 ms	484660 KB	Output is correct
112	Correct	812 ms	175956 KB	Output is correct
113	Correct	819 ms	144236 KB	Output is correct