Submission #1202609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202609		badge881	Sky Walking (IOI19_walk)	C++20	100 / 100	2627 ms	168168 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
#define all(x) x.begin(), x.end()
using namespace std;

const int N = 1e5 + 7;
const long long inf = 1e18;

long long dis[6 * N];
map<int, int> ma[N];
map<int, set<int>> se;
vector<int> ad[N], re[N];
vector<pair<long long, long long>> adj[6 * N];

inline void Edge(int x, int y, int w)
{
    adj[x].push_back({y, w});
    adj[y].push_back({x, w});
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int sta, int en)
{
    int n = x.size(), m = l.size();
    vector<int> v, gl(n, -1), gr(n, -1);
    stack<int> st;
    for (int i = 0; i < n; i++)
    {
        while (!st.empty() && h[st.top()] <= h[i])
            st.pop();
        if (!st.empty())
            gl[i] = st.top();
        st.push(i);
    }
    while (!st.empty())
        st.pop();
    for (int i = n - 1; i >= 0; i--)
    {
        while (!st.empty() && h[st.top()] <= h[i])
            st.pop();
        if (!st.empty())
            gr[i] = st.top();
        st.push(i);
    }

    auto Do = [&](int z)
    {
        v.clear();
        for (int i = 0; i < m; i++)
            if (l[i] < z && z < r[i] && y[i] <= h[z])
            {
                l.push_back(z);
                r.push_back(r[i]);
                y.push_back(y[i]);
                r[i] = z;
            }

        m = l.size();
        for (int i = 0; i < m; i++)
            if (l[i] < z && z < r[i] && y[i] > h[z])
                v.push_back(i);
        sort(all(v), [&](int a, int b)
             { return y[a] < y[b]; });

        int le = z, ri = z;
        for (int i = 0; i < v.size(); i++)
        {
            while (h[le] < y[v[i]])
                le = gl[le];
            while (h[ri] < y[v[i]])
                ri = gr[ri];
            if (le != l[v[i]])
            {
                l.push_back(l[v[i]]);
                r.push_back(le);
                y.push_back(y[v[i]]);
            }
            if (ri != r[v[i]])
            {
                l.push_back(ri);
                r.push_back(r[v[i]]);
                y.push_back(y[v[i]]);
            }
            l[v[i]] = le;
            r[v[i]] = ri;
        }
        m = l.size();
    };

    Do(sta);
    Do(en);

    int cnt = 0;
    ma[sta][0] = cnt++;
    ma[en][0] = cnt++;
    for (int i = 0; i < m; i++)
    {
        if (ma[l[i]].find(y[i]) == ma[l[i]].end())
            ma[l[i]][y[i]] = cnt++;
        if (ma[r[i]].find(y[i]) == ma[r[i]].end())
            ma[r[i]][y[i]] = cnt++;
        ad[l[i]].push_back(y[i]);
        re[r[i]].push_back(y[i]);
        se[y[i]].insert(l[i]);
        se[y[i]].insert(r[i]);
    }

    multiset<int> t;
    t.insert(0);
    for (int i = 0; i < n; i++)
    {
        for (auto it : ad[i])
            t.insert(it);
        auto down = [&](int it)
        {
            int z = *(--t.lower_bound(it));
            if (ma[i].find(z) == ma[i].end())
                ma[i][z] = cnt++;
            Edge(ma[i][it], ma[i][z], it - z);
            se[z].insert(i);
        };
        for (auto it : ad[i])
            down(it);
        for (auto it : re[i])
            down(it);
        for (auto it : re[i])
            t.erase(t.find(it));
    }

    for (int i = 0; i < m; i++)
    {
        auto p = se[y[i]].find(l[i]);
        int la = l[i];
        ++p;
        while (p != se[y[i]].end() && *p <= r[i])
        {
            Edge(ma[la][y[i]], ma[*p][y[i]], x[*p] - x[la]);
            la = *p;
            ++p;
        }
    }

    for (int i = 1; i < cnt; i++)
        dis[i] = inf;
    set<pair<long long, long long>> s;
    s.insert({0, 0});
    while (!s.empty())
    {
        auto p = s.begin();
        int xx = p->second;
        s.erase(p);
        for (auto yy : adj[xx])
        {
            if (dis[xx] + yy.second < dis[yy.first])
            {
                if (dis[yy.first] != inf)
                    s.erase({dis[yy.first], yy.first});
                dis[yy.first] = dis[xx] + yy.second;
                s.insert({dis[yy.first], yy.first});
            }
        }
    }
    if (dis[1] == inf)
        return -1;
    return dis[1];
}

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