oj.uz

Submission #736987

# Submission time Handle Problem Language Result Execution time Memory
736987 2023-05-06T12:14:24 Z finn__ Sky Walking (IOI19_walk) C++17
100 / 100
 2294 ms 222744 KB 
#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

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.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 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 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 340 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 1 ms 212 KB Output is correct
3 Correct 416 ms 91356 KB Output is correct
4 Correct 387 ms 93572 KB Output is correct
5 Correct 281 ms 71648 KB Output is correct
6 Correct 304 ms 65304 KB Output is correct
7 Correct 285 ms 71836 KB Output is correct
8 Correct 476 ms 98136 KB Output is correct
9 Correct 391 ms 86872 KB Output is correct
10 Correct 515 ms 97364 KB Output is correct
11 Correct 355 ms 73004 KB Output is correct
12 Correct 239 ms 56084 KB Output is correct
13 Correct 430 ms 100704 KB Output is correct
14 Correct 296 ms 45584 KB Output is correct
15 Correct 257 ms 51016 KB Output is correct
16 Correct 245 ms 56476 KB Output is correct
17 Correct 247 ms 54432 KB Output is correct
18 Correct 734 ms 71600 KB Output is correct
19 Correct 9 ms 2512 KB Output is correct
20 Correct 99 ms 22500 KB Output is correct
21 Correct 204 ms 55884 KB Output is correct
22 Correct 222 ms 55212 KB Output is correct
23 Correct 511 ms 68200 KB Output is correct
24 Correct 228 ms 56176 KB Output is correct
25 Correct 221 ms 53684 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 21320 KB Output is correct
2 Correct 729 ms 115528 KB Output is correct
3 Correct 756 ms 119772 KB Output is correct
4 Correct 711 ms 121492 KB Output is correct
5 Correct 1000 ms 133744 KB Output is correct
6 Correct 934 ms 119960 KB Output is correct
7 Correct 304 ms 62244 KB Output is correct
8 Correct 203 ms 51908 KB Output is correct
9 Correct 999 ms 113664 KB Output is correct
10 Correct 430 ms 70256 KB Output is correct
11 Correct 9 ms 1108 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 21320 KB Output is correct
2 Correct 729 ms 115528 KB Output is correct
3 Correct 756 ms 119772 KB Output is correct
4 Correct 711 ms 121492 KB Output is correct
5 Correct 1000 ms 133744 KB Output is correct
6 Correct 934 ms 119960 KB Output is correct
7 Correct 304 ms 62244 KB Output is correct
8 Correct 203 ms 51908 KB Output is correct
9 Correct 999 ms 113664 KB Output is correct
10 Correct 430 ms 70256 KB Output is correct
11 Correct 9 ms 1108 KB Output is correct
12 Correct 756 ms 119176 KB Output is correct
13 Correct 601 ms 121172 KB Output is correct
14 Correct 1084 ms 133632 KB Output is correct
15 Correct 559 ms 92292 KB Output is correct
16 Correct 584 ms 99860 KB Output is correct
17 Correct 735 ms 122200 KB Output is correct
18 Correct 561 ms 92292 KB Output is correct
19 Correct 571 ms 99876 KB Output is correct
20 Correct 342 ms 60948 KB Output is correct
21 Correct 24 ms 2916 KB Output is correct
22 Correct 394 ms 92264 KB Output is correct
23 Correct 366 ms 84872 KB Output is correct
24 Correct 291 ms 56324 KB Output is correct
25 Correct 324 ms 77844 KB Output is correct
26 Correct 256 ms 41344 KB Output is correct
27 Correct 1118 ms 131932 KB Output is correct
28 Correct 485 ms 119020 KB Output is correct
29 Correct 989 ms 119932 KB Output is correct
30 Correct 303 ms 61908 KB Output is correct
31 Correct 950 ms 113520 KB Output is correct
32 Correct 310 ms 61100 KB Output is correct
33 Correct 299 ms 60588 KB Output is correct
34 Correct 411 ms 65640 KB Output is correct
35 Correct 364 ms 69988 KB Output is correct
36 Correct 232 ms 57176 KB Output is correct
37 Correct 208 ms 53068 KB Output is correct
38 Correct 222 ms 51860 KB Output is correct
39 Correct 580 ms 65148 KB Output is correct
40 Correct 219 ms 53096 KB Output is correct
41 Correct 218 ms 51000 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 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 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 340 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 416 ms 91356 KB Output is correct
21 Correct 387 ms 93572 KB Output is correct
22 Correct 281 ms 71648 KB Output is correct
23 Correct 304 ms 65304 KB Output is correct
24 Correct 285 ms 71836 KB Output is correct
25 Correct 476 ms 98136 KB Output is correct
26 Correct 391 ms 86872 KB Output is correct
27 Correct 515 ms 97364 KB Output is correct
28 Correct 355 ms 73004 KB Output is correct
29 Correct 239 ms 56084 KB Output is correct
30 Correct 430 ms 100704 KB Output is correct
31 Correct 296 ms 45584 KB Output is correct
32 Correct 257 ms 51016 KB Output is correct
33 Correct 245 ms 56476 KB Output is correct
34 Correct 247 ms 54432 KB Output is correct
35 Correct 734 ms 71600 KB Output is correct
36 Correct 9 ms 2512 KB Output is correct
37 Correct 99 ms 22500 KB Output is correct
38 Correct 204 ms 55884 KB Output is correct
39 Correct 222 ms 55212 KB Output is correct
40 Correct 511 ms 68200 KB Output is correct
41 Correct 228 ms 56176 KB Output is correct
42 Correct 221 ms 53684 KB Output is correct
43 Correct 94 ms 21320 KB Output is correct
44 Correct 729 ms 115528 KB Output is correct
45 Correct 756 ms 119772 KB Output is correct
46 Correct 711 ms 121492 KB Output is correct
47 Correct 1000 ms 133744 KB Output is correct
48 Correct 934 ms 119960 KB Output is correct
49 Correct 304 ms 62244 KB Output is correct
50 Correct 203 ms 51908 KB Output is correct
51 Correct 999 ms 113664 KB Output is correct
52 Correct 430 ms 70256 KB Output is correct
53 Correct 9 ms 1108 KB Output is correct
54 Correct 756 ms 119176 KB Output is correct
55 Correct 601 ms 121172 KB Output is correct
56 Correct 1084 ms 133632 KB Output is correct
57 Correct 559 ms 92292 KB Output is correct
58 Correct 584 ms 99860 KB Output is correct
59 Correct 735 ms 122200 KB Output is correct
60 Correct 561 ms 92292 KB Output is correct
61 Correct 571 ms 99876 KB Output is correct
62 Correct 342 ms 60948 KB Output is correct
63 Correct 24 ms 2916 KB Output is correct
64 Correct 394 ms 92264 KB Output is correct
65 Correct 366 ms 84872 KB Output is correct
66 Correct 291 ms 56324 KB Output is correct
67 Correct 324 ms 77844 KB Output is correct
68 Correct 256 ms 41344 KB Output is correct
69 Correct 1118 ms 131932 KB Output is correct
70 Correct 485 ms 119020 KB Output is correct
71 Correct 989 ms 119932 KB Output is correct
72 Correct 303 ms 61908 KB Output is correct
73 Correct 950 ms 113520 KB Output is correct
74 Correct 310 ms 61100 KB Output is correct
75 Correct 299 ms 60588 KB Output is correct
76 Correct 411 ms 65640 KB Output is correct
77 Correct 364 ms 69988 KB Output is correct
78 Correct 232 ms 57176 KB Output is correct
79 Correct 208 ms 53068 KB Output is correct
80 Correct 222 ms 51860 KB Output is correct
81 Correct 580 ms 65148 KB Output is correct
82 Correct 219 ms 53096 KB Output is correct
83 Correct 218 ms 51000 KB Output is correct
84 Correct 84 ms 17780 KB Output is correct
85 Correct 763 ms 127112 KB Output is correct
86 Correct 1609 ms 174160 KB Output is correct
87 Correct 65 ms 11964 KB Output is correct
88 Correct 54 ms 12816 KB Output is correct
89 Correct 48 ms 11952 KB Output is correct
90 Correct 21 ms 6160 KB Output is correct
91 Correct 1 ms 440 KB Output is correct
92 Correct 16 ms 4836 KB Output is correct
93 Correct 201 ms 45568 KB Output is correct
94 Correct 33 ms 5404 KB Output is correct
95 Correct 416 ms 100988 KB Output is correct
96 Correct 372 ms 89308 KB Output is correct
97 Correct 318 ms 60272 KB Output is correct
98 Correct 315 ms 81460 KB Output is correct
99 Correct 2294 ms 222744 KB Output is correct
100 Correct 611 ms 124844 KB Output is correct
101 Correct 1264 ms 153116 KB Output is correct
102 Correct 270 ms 65284 KB Output is correct
103 Correct 300 ms 64184 KB Output is correct
104 Correct 309 ms 63608 KB Output is correct
105 Correct 482 ms 68392 KB Output is correct
106 Correct 320 ms 61156 KB Output is correct
107 Correct 381 ms 58812 KB Output is correct
108 Correct 40 ms 9844 KB Output is correct
109 Correct 706 ms 98940 KB Output is correct
110 Correct 574 ms 124416 KB Output is correct
111 Correct 564 ms 124928 KB Output is correct
112 Correct 344 ms 70680 KB Output is correct
113 Correct 301 ms 68792 KB Output is correct