Submission #413581

#	Time	Username	Problem	Language	Result	Execution time	Memory
413581		timmyfeng	Sky Walking (IOI19_walk)	C++17	100 / 100	1833 ms	160332 KiB

walk

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

struct segtree {
    segtree *left, *right;
    int value;

    segtree(int l, int r) {
        if (l == r) {
            value = 0;
        } else {
            value = -1;
            int m = (l + r) / 2;
            left = new segtree(l, m);
            right = new segtree(m + 1, r);
        }
    }

    void push() {
        if (value != -1) {
            left->value = right->value = value;
            value = -1;
        }
    }

    void update(int x, int a, int b, int l, int r) {
        if (b < l || r < a) {
            return;
        } else if (a <= l && r <= b) {
            value = x;
        } else {
            push();
            int m = (l + r) / 2;
            left->update(x, a, b, l, m);
            right->update(x, a, b, m + 1, r);
        }
    }

    int query(int a, int l, int r) {
        if (l == r) {
            return value;
        } else {
            push();
            int m = (l + r) / 2;
            if (a <= m) {
                return left->query(a, l, m);
            } else {
                return right->query(a, m + 1, r);
            }
        }
    }
};

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
    int n = x.size(), m = y.size();

    vector<array<int, 3>> events;
    for (int i = 0; i < n; ++i) {
        events.push_back({h[i], INT_MAX, i});
    }
    for (int i = 0; i < m; ++i) {
        events.push_back({y[i], l[i], r[i]});
    }
    sort(events.begin(), events.end());

    set<int> buildings;
    for (int i = 0; i < n; ++i) {
        buildings.insert(i);
    }

    vector<map<int, vector<array<int, 2>>>> adj(n);
    segtree *prv = new segtree(0, n - 1);
    vector<array<int, 3>> skywalks;
    map<int, set<int>> nodes;

    for (auto [i, a, b] : events) {
        if (a == INT_MAX) {
            buildings.erase(b);
        } else {
            set<int> segments = {a, b};
            for (auto j : {s, g}) {
                auto it = buildings.lower_bound(j);
                if (it != buildings.end()) {
                    segments.insert(*it);
                }

                it = buildings.upper_bound(j);
                if (it != buildings.begin()) {
                    segments.insert(*--it);
                }
            }

            while (*segments.begin() < a) {
                segments.erase(segments.begin());
            }
            while (*--segments.end() > b) {
                segments.erase(--segments.end());
            }

            for (auto j : segments) {
                int k = prv->query(j, 0, n - 1);
                adj[j][k].push_back({j, i});
                adj[j][i].push_back({j, k});
                nodes[k].insert(j);
                nodes[i].insert(j);
            }

            prv->update(i, a, b, 0, n - 1);
        }
    }

    for (int i = 0; i < m; ++i) {
        auto it = nodes[y[i]].lower_bound(l[i]);
        while (*it != r[i]) {
            auto nxt = it; ++nxt;
            adj[*nxt][y[i]].push_back({*it, y[i]});
            adj[*it][y[i]].push_back({*nxt, y[i]});
            it = nxt;
        }
    }

    priority_queue<tuple<long long, int, int>> dijkstra;
    vector<map<int, long long>> dist(n);
    dijkstra.push({0, s, 0});
    dist[s][0] = 0;

    while (!dijkstra.empty()) {
        auto [d, i, j] = dijkstra.top();
        dijkstra.pop();
        d = -d;

        if (d > dist[i][j]) {
            continue;
        }

        if (i == g && j == 0) {
            return d;
        }

        for (auto [ic, jc] : adj[i][j]) {
            int w = i == ic ? abs(j - jc) : abs(x[i] - x[ic]);
            if (dist[ic].count(jc) == 0 || d + w < dist[ic][jc]) {
                dijkstra.push({-(d + w), ic, jc});
                dist[ic][jc] = d + w;
            }
        }
    }

    return -1;
}

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