Submission #198835

#	Time	Username	Problem	Language	Result	Execution time	Memory
198835		imeimi2000	Sky Walking (IOI19_walk)	C++17	57 / 100	4313 ms	385796 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 = 1e18;
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 solve12(int s, int e) {
    int idx = n;
    vector<vector<pii>> P(n + 1);
    vector<int> S[20];
    for (int i = 0; i < 20; ++i) S[i] = vector<int>(n + 1);
    for (int i = 1; i <= n; ++i) {
        P[i].emplace_back(0, i);
        S[0][i] = H[i];
    }
    for (int i = 1; i < 20; ++i) {
        for (int j = 1; j <= n; ++j) {
            S[i][j] = S[i - 1][j];
            int k = j + (1 << i - 1);
            if (k <= n) S[i][j] = max(S[i][j], S[i - 1][k]);
        }
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = L[i]; ; ++j) {
            P[j].emplace_back(Y[i], ++idx);
            if (j == R[i]) break;
            for (int k = 20; k--; ) {
                if (S[k][j + 1] < Y[i]) j += 1 << k;
            }
        }
    }
    vector<vector<pii>> edge(idx + 1);
    auto add_edge = [&](int a, int b, int c) {
        edge[a].emplace_back(b, c);
        edge[b].emplace_back(a, c);
    };
    for (int i = 1; i <= n; ++i) {
        sort(P[i].begin(), P[i].end());
        for (int j = 1; j < int(P[i].size()); ++j) {
            add_edge(P[i][j - 1].se, P[i][j].se, P[i][j].fs - P[i][j - 1].fs);
        }
    }
    for (int i = 1; i <= m; ++i) {
        int pri = -1, prx;
        for (int j = L[i]; ; ++j) {
            if (Y[i] > H[j]) continue;
            int it = lower_bound(P[j].begin(), P[j].end(), pii(Y[i], 0))->se;
            if (pri != -1) add_edge(pri, it, X[j] - prx);
            pri = it;
            prx = X[j];
            if (j == R[i]) break;
            for (int k = 20; k--; ) {
                if (S[k][j + 1] < Y[i]) j += 1 << k;
            }
        }
    }
    return dijkstra(s, e, edge);
}

llong solve34() {
    vector<vector<int>> P(n + 1), S(n + 1), E(n + 1);
    P[1].push_back(0);
    P[n].push_back(0);
    S[1].push_back(0);
    E[n].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]);
    }
    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;
        for (int j : P[i]) {
            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(j, x);
            }
        }
        vector<int> N;
        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 || V[0].fs != 1 || V.back().fs != n) return -1;
    int 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 (n == 1) 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];
    }
    if (s == 0 && g == n - 1) {
        return solve34();
    }
    return solve12(s + 1, g + 1);
}

Compilation message (stderr)

walk.cpp: In function 'llong solve12(int, int)':
walk.cpp:55:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
             int k = j + (1 << i - 1);
                               ~~^~~
walk.cpp:84:36: warning: 'prx' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if (pri != -1) add_edge(pri, it, X[j] - prx);
                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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