oj.uz

Submission #424537

# Submission time Handle Problem Language Result Execution time Memory
424537 2021-06-12T04:56:29 Z yuto1115 Sky Walking (IOI19_walk) C++17
0 / 100
 2467 ms 164772 KB 
#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(n, linf), init2(n, 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]) {
                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++]);
                }
                int cnt = 0;
                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 == linf ? -1 : ans);
}

Compilation message

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;
      |                ~~^~~~~~~~~~~~~
walk.cpp: In function 'll min_distance(vi, vi, vi, vi, vi, int, int)':
walk.cpp:145:21: warning: unused variable 'cnt' [-Wunused-variable]
  145 |                 int cnt = 0;
      |                     ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1578 ms 114204 KB Output is correct
4 Correct 1564 ms 118780 KB Output is correct
5 Correct 1101 ms 101412 KB Output is correct
6 Correct 938 ms 88604 KB Output is correct
7 Correct 1082 ms 101344 KB Output is correct
8 Correct 2054 ms 144988 KB Output is correct
9 Correct 1342 ms 101360 KB Output is correct
10 Correct 2467 ms 164772 KB Output is correct
11 Correct 973 ms 60972 KB Output is correct
12 Incorrect 265 ms 37060 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8444 KB Output is correct
2 Runtime error 233 ms 28740 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8444 KB Output is correct
2 Runtime error 233 ms 28740 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Halted 0 ms 0 KB -