Submission #801542

#	Time	Username	Problem	Language	Result	Execution time	Memory
801542		resting	Sky Walking (IOI19_walk)	C++17	100 / 100	3081 ms	144392 KiB

walk

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

#define ll long long

const int inf = 1e9;

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
    int n = x.size(), m = l.size();
    vector<pair<int, pair<int, int>>> a, b, c;
    for (int i = 0; i < m; i++) a.push_back({ y[i], {l[i], r[i]} });
    sort(a.begin(), a.end());
    vector<pair<int, int>> bld;
    for (int i = 0; i < n; i++) bld.push_back({ h[i], i });
    bld.push_back({ 0, -1 }); // just for the sake of it
    sort(bld.begin(), bld.end());
#define uwu(s, sign, mn, st)\
    {\
        int rght = st;\
        for (int i = n - 1; i >= 0; i--) {\
            while (a.size() && a.back().first > bld[i].first) {\
                if (a.back().second.first < rght && a.back().second.second > rght) {\
                    b.push_back({ a.back().first, {a.back().second.first, rght } });\
                    b.push_back({ a.back().first, {rght, a.back().second.second } });\
                }\
                else b.push_back(a.back());\
                a.pop_back();\
            }\
            if (bld[i].second sign s)\
                rght = mn(rght, bld[i].second);\
        }\
        swap(a, b); reverse(a.begin(), a.end());\
    }

    uwu(s, >= , min, inf);
    uwu(s, <= , max, -inf);
    uwu(g, >= , min, inf);
    uwu(g, <= , max, -inf);
    reverse(a.begin(), a.end());
    set<pair<int, int>> pts; // set of points
    map<pair<int, int>, vector<pair<int, int>>> adj;
    auto edge = [&](pair<int, int> a, pair<int, int> b) {
        adj[a].push_back(b); adj[b].push_back(a);
    };
    auto dist = [&](pair<int, int> a, pair<int, int> b) -> ll {
        return (ll)(abs(x[a.first] - x[b.first]) + abs(a.second - b.second));
    };
    for (auto& x : a) {
        int prev = x.second.first;
        auto pt = pts.lower_bound({ x.second.first, 0 });
        while (pt != pts.end() && pt->first <= x.second.second) {
            edge({ pt->first, x.first }, { prev, x.first });
            edge({ pt->first, x.first }, { pt->first, pt->second });
            prev = pt->first;
            pts.erase(pt++);
        }
        edge({ x.second.second, x.first }, { prev, x.first });
        pts.insert({ x.second.first, x.first });
        pts.insert({ x.second.second, x.first });
    }
    for (auto& x : pts) {
        edge({ x.first, x.second }, { x.first, 0 });
    }

    map<pair<int, int>, ll> dst;
    set<pair<ll, pair<int, int>>> q;
    q.insert({ 1, {s, 0} });
    while (!q.empty()) {
        auto t = *q.begin();
        q.erase(q.begin());
        if (dst[t.second]) continue;
        dst[t.second] = t.first;
        for (auto& x : adj[t.second]) {
            q.insert({ dist(t.second, x) + t.first,  x });
        }
    }
    return dst[{g, 0}] - 1;
}

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