Submission #736987

#	Time	Username	Problem	Language	Result	Execution time	Memory
736987		finn__	Sky Walking (IOI19_walk)	C++17	100 / 100	2294 ms	222744 KiB

walk

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using L = long long;

vector<size_t> last_node;
vector<vector<pair<size_t, L>>> G;
vector<pair<L, L>> p;
vector<L> d;
vector<pair<size_t, bool>> events;

void split_walks(vector<int> const &x, vector<int> const &h, vector<int> &l,
                 vector<int> &r, vector<int> &y, size_t j)
{
    vector<size_t> left_greater, right_greater, to_erase;
    for (size_t i = 0; i <= j; ++i)
    {
        while (!left_greater.empty() && h[i] >= h[left_greater.back()])
            left_greater.pop_back();
        left_greater.push_back(i);
    }
    for (size_t i = x.size() - 1; i >= j && i < x.size(); --i)
    {
        while (!right_greater.empty() && h[i] >= h[right_greater.back()])
            right_greater.pop_back();
        right_greater.push_back(i);
    }

    size_t const m = l.size();
    for (size_t i = 0; i < m; ++i)
        if (l[i] < j && j < r[i])
        {
            size_t a = 0, b = left_greater.size() - 1;
            while (a < b)
            {
                size_t const mid = (a + b + 1) / 2;
                if (h[left_greater[mid]] >= y[i])
                    a = mid;
                else
                    b = mid - 1;
            }
            size_t const u = left_greater[a];
            a = 0, b = right_greater.size() - 1;
            while (a < b)
            {
                size_t const mid = (a + b + 1) / 2;
                if (h[right_greater[mid]] >= y[i])
                    a = mid;
                else
                    b = mid - 1;
            }
            size_t const v = right_greater[a];
            if (l[i] != u)
            {
                l.push_back(l[i]);
                r.push_back(u);
                y.push_back(y[i]);
            }
            if (u != v)
            {
                l.push_back(u);
                r.push_back(v);
                y.push_back(y[i]);
            }
            if (r[i] != v)
            {
                l.push_back(v);
                r.push_back(r[i]);
                y.push_back(y[i]);
            }
            to_erase.push_back(i);
        }
    for (size_t const &i : to_erase)
    {
        swap(l[i], l.back()), l.pop_back();
        swap(r[i], r.back()), r.pop_back();
        swap(y[i], y.back()), y.pop_back();
    }
}

L min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r,
               vector<int> y, int s, int g)
{
    split_walks(x, h, l, r, y, s);
    split_walks(x, h, l, r, y, g);

    size_t const m = l.size();
    last_node.resize(m);
    fill(last_node.begin(), last_node.end(), SIZE_MAX);
    for (size_t i = 0; i < m; ++i)
        events.emplace_back(i, 0), events.emplace_back(i, 1);
    sort(events.begin(), events.end(), [&](auto const &u, auto const &v)
         { int const a = u.second ? r[u.first] : l[u.first],
                     b = v.second ? r[v.first] : l[v.first];
           return a == b ? !u.second && v.second : a < b; });

    auto compare_segment_height = [&](size_t const &i, size_t const &j)
    { return y[i] < y[j]; };

    multiset<size_t, decltype(compare_segment_height)> segments(compare_segment_height);
    map<pair<L, L>, size_t> nodes;

    auto get_node = [&](L const &i, L const &j)
    {
        auto it = nodes.find({i, j});
        if (it != nodes.end())
            return it->second;
        nodes[{i, j}] = G.size();
        p.emplace_back(i, j);
        G.emplace_back();
        return G.size() - 1;
    };

    for (auto const &[i, b] : events)
    {
        size_t const curr_node = get_node(b ? x[r[i]] : x[l[i]], y[i]);
        if (last_node[i] != SIZE_MAX)
        {
            G[curr_node].emplace_back(last_node[i], p[curr_node].first - p[last_node[i]].first);
            G[last_node[i]].emplace_back(curr_node, p[curr_node].first - p[last_node[i]].first);
        }
        last_node[i] = curr_node;
        if (b)
            segments.erase(segments.find(i));
        auto it = segments.upper_bound(i);
        if (it != segments.end() && h[b ? r[i] : l[i]] >= y[*it])
        {
            size_t const neighbor = get_node(b ? x[r[i]] : x[l[i]], y[*it]);
            G[curr_node].emplace_back(neighbor, y[*it] - y[i]);
            G[neighbor].emplace_back(curr_node, y[*it] - y[i]);
            if (neighbor != last_node[*it])
            {
                G[neighbor].emplace_back(last_node[*it], p[neighbor].first - p[last_node[*it]].first);
                G[last_node[*it]].emplace_back(neighbor, p[neighbor].first - p[last_node[*it]].first);
            }
            last_node[*it] = neighbor;
        }
        it = segments.lower_bound(i);
        if (!segments.empty() && it != segments.begin() && y[*prev(it)] < y[i])
        {
            --it;
            size_t const neighbor = get_node(b ? x[r[i]] : x[l[i]], y[*it]);
            G[curr_node].emplace_back(neighbor, y[i] - y[*it]);
            G[neighbor].emplace_back(curr_node, y[i] - y[*it]);
            if (neighbor != last_node[*it])
            {
                G[neighbor].emplace_back(last_node[*it], p[neighbor].first - p[last_node[*it]].first);
                G[last_node[*it]].emplace_back(neighbor, p[neighbor].first - p[last_node[*it]].first);
            }
            last_node[*it] = neighbor;
        }
        if (!b)
            segments.insert(i);
    }

    size_t const t = get_node(x[g], 0);
    for (size_t i = 0; i < G.size(); ++i)
        if (p[i].first == x[g])
            G[i].emplace_back(t, p[i].second);
    priority_queue<pair<L, size_t>> q;
    d.resize(G.size());
    fill(d.begin(), d.end(), LLONG_MAX);
    for (size_t i = 0; i < G.size(); ++i)
        if (p[i].first == x[s])
            d[i] = p[i].second, q.emplace(-d[i], i);

    while (!q.empty())
    {
        auto const [f, u] = q.top();
        q.pop();
        if (-f != d[u])
            continue;
        if (u == t)
            return -f;
        for (auto const &[v, w] : G[u])
            if (-f + w < d[v])
            {
                d[v] = -f + w;
                q.emplace(-d[v], v);
            }
    }
    return -1;
}

Compilation message (stderr)

walk.cpp: In function 'void split_walks(const std::vector<int>&, const std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, size_t)':
walk.cpp:34:18: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         if (l[i] < j && j < r[i])
walk.cpp:34:27: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   34 |         if (l[i] < j && j < r[i])
walk.cpp:56:22: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   56 |             if (l[i] != u)
walk.cpp:68:22: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   68 |             if (r[i] != v)

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