Submission #424608

#	Time	Username	Problem	Language	Result	Execution time	Memory
424608		yuto1115	Sky Walking (IOI19_walk)	C++17	0 / 100	44 ms	14100 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;

const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

class RmQ {
    int n;
    vl v;
public:
    RmQ(vl init) {
        n = 1;
        while (n < init.size()) n *= 2;
        v.assign(2 * n, linf);
        rep(i, init.size()) v[n + i] = init[i];
        rrep(i, n) v[i] = min(v[2 * i], v[2 * i + 1]);
    }
    
    void update(int i, ll x) {
        assert(0 <= i and i < n);
        i += n;
        v[i] = x;
        while (i > 1) {
            i >>= 1;
            v[i] = min(v[2 * i], v[2 * i + 1]);
        }
    }
    
    ll prod(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        ll res = linf;
        while (l < r) {
            if (l & 1) chmin(res, v[l++]);
            if (r & 1) chmin(res, v[--r]);
            l >>= 1, r >>= 1;
        }
        return res;
    }
};

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
    int n = x.size();
    int m = l.size();
    ll ans;
    if (s == 0 and g == n - 1) {
        vi zip = y;
        sort(all(zip));
        zip.erase(unique(all(zip)), zip.end());
        int sz = zip.size();
        rep(i, m) y[i] = lower_bound(all(zip), y[i]) - zip.begin();
        vvi ad(n), er(n);
        {
            vector<set<int>> na(n), ne(n);
            rep(i, m) {
                na[l[i]].insert(y[i]);
                ne[r[i]].insert(y[i]);
            }
            rep(i, n) {
                for (int j : na[i]) {
                    if (!ne[i].count(j)) ad[i].pb(j);
                }
                for (int j : ne[i]) {
                    if (!na[i].count(j)) er[i].pb(j);
                }
            }
        }
        // 1 -> value + height
        // 2 -> value - height
        vl init1(sz, linf), init2(sz, linf);
        for (int i : ad[0]) {
            init1[i] = zip[i] * 2;
            init2[i] = 0;
        }
        RmQ st1(init1), st2(init2);
        rep2(i, 1, n) {
            int ub = upper_bound(all(zip), h[i]) - zip.begin();
            for (int j : ad[i]) {
                assert(st1.prod(j, j + 1) == linf);
                assert(st2.prod(j, j + 1) == linf);
                ll now = linf;
                chmin(now, zip[j] + st2.prod(0, j));
                chmin(now, -zip[j] + st1.prod(j + 1, ub));
                st1.update(j, now + zip[j]);
                st2.update(j, now - zip[j]);
            }
            for (int j : er[i]) {
                st1.update(j, linf);
                st2.update(j, linf);
            }
        }
        ans = st1.prod(0, sz) + x.back() - x[0];
    } else {
        vp pos;
        pos.eb(s, 0);
        pos.eb(g, 0);
        vi ob(n);
        iota(all(ob), 0);
        sort(all(ob), [&](int i, int j) { return h[i] < h[j]; });
        vi oe(m);
        iota(all(oe), 0);
        sort(all(oe), [&](int i, int j) { return y[i] < y[j]; });
        {
            set<int> st;
            rep(i, n) st.insert(i);
            int it = 0;
            for (int i : oe) {
                while (it < n and h[ob[it]] < y[i]) {
                    st.erase(ob[it++]);
                }
                auto now = st.lower_bound(l[i]);
                while (now != st.end() and *now <= r[i]) {
                    pos.eb(*now, y[i]);
                    now++;
                }
            }
        }
        sort(all(pos));
        pos.erase(unique(all(pos)), pos.end());
        int sz = pos.size();
        map<P, int> id;
        rep(i, sz) id[pos[i]] = i;
        vvp G(sz);
        rep(i, sz - 1) if (pos[i].first == pos[i + 1].first) {
                G[i].eb(i + 1, pos[i + 1].second - pos[i].second);
                G[i + 1].eb(i, pos[i + 1].second - pos[i].second);
            }
        {
            set<int> st;
            rep(i, n) st.insert(i);
            int it = 0;
            for (int i : oe) {
                while (it < n and h[ob[it]] < y[i]) {
                    st.erase(ob[it++]);
                }
                auto now = st.lower_bound(l[i]);
                int pre = -1;
                while (now != st.end() and *now <= r[i]) {
                    int nx = id[{*now, y[i]}];
                    if (pre >= 0) {
                        assert(pos[nx].first >= pos[pre].first);
                        G[pre].eb(nx, x[pos[nx].first] - x[pos[pre].first]);
                        G[nx].eb(pre, x[pos[nx].first] - x[pos[pre].first]);
                    }
                    pre = nx;
                    now++;
                }
            }
        }
        vl dist(sz, linf);
        using lp = pair<ll, int>;
        priority_queue<lp, vector<lp>, greater<lp>>
            pq;
        dist[id[{s, 0}]] = 0;
        pq.emplace(0, id[{s, 0}]);
        while (!pq.empty()) {
            auto[d, u] = pq.top();
            pq.pop();
            if (dist[u] < d) continue;
            for (auto[v, len] : G[u]) {
                if (chmin(dist[v], d + len)) pq.emplace(d + len, v);
            }
        }
        ans = dist[id[{g, 0}]];
    }
    return (ans >= 1e17 ? -1 : ans);
}

Compilation message (stderr)

walk.cpp: In constructor 'RmQ::RmQ(vl)':
walk.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         while (n < init.size()) n *= 2;
      |                ~~^~~~~~~~~~~~~

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