Submission #602273

#	Time	Username	Problem	Language	Result	Execution time	Memory
602273		Johann	Sky Walking (IOI19_walk)	C++14	33 / 100	122 ms	13936 KiB

walk

// #include "walk.h"
// bruteForce sub 3
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef tuple<int, int, int> tiii;
typedef vector<bool> vb;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
#define F0R(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int maxN = 10005;
const ll INF = LLONG_MAX;

ll min_distance(vpii &B, vtiii &S, int s, int g) {
    int n = sz(B);
    int m = sz(S);
    map<ll, pii> dp; // höhe : { value, expiryIndex }
    dp[0] = {0, n - 1};

    // Sortierung nach Endpunkt dann von Hinten zum Ziel
    sort(all(S), [&](tiii &a, tiii &b) {
        if (get<1>(a) != get<1>(b)) return get<1>(a) > get<1>(b);
        return get<2>(a) < get<2>(b);
    });

    int i = 0;
    while (i < m) {
        tiii seg = S[i];
        if (sz(dp) == 0) return -1;
        ll l, r, y;
        tie(l, r, y) = seg;
        ll d = INF;
        // Oberhalb:
        auto ito = dp.lower_bound(y);
        if (ito != dp.end()) {
            if (ito->second.second > r) {
                dp.erase(ito);
                continue;
            }
            d = min(d, ito->second.first + abs(ito->first - y));
        }
        // Unterhalb:
        auto itu = dp.lower_bound(y);
        if (itu != dp.begin()) {
            --itu;
            if (itu->second.second > r) {
                dp.erase(itu);
                continue;
            }
            d = min(d, itu->second.first + abs(itu->first - y));
        }
        // Antwort eintragen
        dp[y] = {d, l};
        ++i;
    }
    ll ans = INF;
    for (auto it = dp.begin(); it != dp.end(); ++it) {
        if (it->second.second > s) continue;
        ans = min(ans, it->second.first + it->first);
    }
    if (ans == INF) return -1;
    return ans + B[g].first - B[s].first;
}

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) {
// ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
    int n = sz(x), m = sz(l);
    if (g < s) swap(g, s);
    vtiii segs(m);
    vpii B(n);
    F0R(i, n) B[i] = {x[i], h[i]};
    F0R(i, m) segs[i] = {l[i], r[i], y[i]};
    return min_distance(B, segs, s, g);
}

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