Submission #198859

#	Time	Username	Problem	Language	Result	Execution time	Memory
198859		imeimi2000	Sky Walking (IOI19_walk)	C++17	100 / 100	2559 ms	122792 KiB

walk

#include "walk.h"
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const llong inf = 4e18;
int n, m;
int X[100001], H[100001];
int L[100001], R[100001], Y[100001];

llong dijkstra(int s, int e, const vector<vector<pii>> &edge) {
    int n = int(edge.size()) - 1;
    vector<llong> D(n + 1, inf);
    priority_queue<pll> pq;
    D[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        llong x, d;
        tie(d, x) = pq.top();
        pq.pop();
        d = -d;
        if (D[x] != d) continue;
        for (pii i : edge[x]) {
            llong nd = d + i.se;
            if (nd < D[i.fs]) {
                D[i.fs] = nd;
                pq.emplace(-nd, i.fs);
            }
        }
    }
    return D[e] < inf ? D[e] : -1;
}

llong solve(int st, int ed) {
    vector<vector<int>> P(n + 1), S(n + 1), E(n + 1), M(20, vector<int>(n + 1));
    for (int i = 1; i <= n; ++i) {
        M[0][i] = H[i];
    }
    for (int i = 1; i < 20; ++i) {
        for (int j = 1; j <= n; ++j) {
            M[i][j] = M[i - 1][j];
            int k = j + (1 << i - 1);
            if (k <= n) M[i][j] = max(M[i][j], M[i - 1][k]);
        }
    }
    P[st].push_back(0);
    P[ed].push_back(0);
    S[st].push_back(0);
    S[ed].push_back(0);
    E[st].push_back(0);
    E[ed].push_back(0);
    for (int i = 1; i <= m; ++i) {
        P[L[i]].push_back(Y[i]);
        P[R[i]].push_back(Y[i]);
        S[L[i]].push_back(Y[i]);
        E[R[i]].push_back(Y[i]);
        if (L[i] < st && st < R[i]) {
            int prv = st, nxt = st;
            for (int b = 20; b--; ) {
                if (M[b][nxt] < Y[i]) nxt += (1 << b);
                if ((1 << b) < prv && M[b][prv - (1 << b) + 1] < Y[i]) prv -= (1 << b);
            }
            P[prv].push_back(Y[i]);
            P[nxt].push_back(Y[i]);
        }
        if (L[i] < ed && ed < R[i]) {
            int prv = ed, nxt = ed;
            for (int b = 20; b--; ) {
                if (M[b][nxt] < Y[i]) nxt += (1 << b);
                if ((1 << b) < prv && M[b][prv - (1 << b) + 1] < Y[i]) prv -= (1 << b);
            }
            P[prv].push_back(Y[i]);
            P[nxt].push_back(Y[i]);
        }
    }
    map<int, vector<pii>> I;
    vector<vector<pii>> edge(1);
    auto add_edge = [&](int a, int b, int c) {
        edge[a].emplace_back(b, c);
        edge[b].emplace_back(a, c);
    };
    multiset<int> sp;
    int idx = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j : S[i]) sp.insert(j);
        sort(P[i].begin(), P[i].end());
        P[i].erase(unique(P[i].begin(), P[i].end()), P[i].end());
        vector<pii> V;
        vector<int> N;
        for (int j : P[i]) {
            N.push_back(j);
            auto itL = sp.lower_bound(j);
            auto itU = sp.upper_bound(j);
            if (itL != sp.begin()) {
                int x = *prev(itL);
                V.emplace_back(j, x);
            }
            if (itU != sp.end() && *itU <= H[i]) {
                int x = *itU;
                V.emplace_back(x, j);
            }
        }
        sort(V.begin(), V.end());
        V.erase(unique(V.begin(), V.end()), V.end());
        for (pii j : V) {
            N.push_back(j.fs);
            N.push_back(j.se);
        }
        sort(N.begin(), N.end());
        N.erase(unique(N.begin(), N.end()), N.end());
        edge.resize(edge.size() + N.size());
        for (pii j : V) {
            int a = upper_bound(N.begin(), N.end(), j.fs) - N.begin() + idx;
            int b = upper_bound(N.begin(), N.end(), j.se) - N.begin() + idx;
            add_edge(a, b, abs(j.fs - j.se));
        }
        for (int j : N) I[j].emplace_back(i, ++idx);
        for (int j : E[i]) sp.erase(sp.find(j));
    }
    for (int i = 1; i <= m; ++i) {
        const vector<pii> &V = I[Y[i]];
        auto it = lower_bound(V.begin(), V.end(), pii(L[i], 0));
        int pri = -1, prx;
        while (it != V.end() && it->fs <= R[i]) {
            if (pri != -1) add_edge(pri, it->se, X[it->fs] - prx);
            prx = X[it->fs];
            pri = it->se;
            ++it;
        }
    }
    const vector<pii> &V = I[0];
    if (int(V.size()) < 2) return -1;
    st = V[0].se, ed = V.back().se;
    return dijkstra(st, ed, edge);
}

llong min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = x.size();
    if (s == g) return 0;
    m = l.size();
    for (int i = 1; i <= n; ++i) {
        X[i] = x[i - 1];
        H[i] = h[i - 1];
    }
    for (int i = 1; i <= m; ++i) {
        L[i] = l[i - 1] + 1;
        R[i] = r[i - 1] + 1;
        Y[i] = y[i - 1];
    }
    return solve(s + 1, g + 1);
}

Compilation message (stderr)

walk.cpp: In function 'llong solve(int, int)':
walk.cpp:51:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
             int k = j + (1 << i - 1);
                               ~~^~~

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