oj.uz

Submission #424613

# Submission time Handle Problem Language Result Execution time Memory
424613 2021-06-12T07:51:39 Z yuto1115 Sky Walking (IOI19_walk) C++17
25 / 100
 2326 ms 162820 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);
        l += n, 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 - 1) {
//            cerr << "bf " << i << endl;
//            rep(j, sz) {
//                cerr << ' ' << j << endl;
//                cerr << "  " << st1.prod(j, j + 1) << endl;
//                cerr << "  " << st2.prod(j, j + 1) << endl;
//            }
            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++]);
                }
                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

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
10.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 360 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 420 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 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 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1668 ms 112596 KB Output is correct
4 Correct 1676 ms 116632 KB Output is correct
5 Correct 1132 ms 99156 KB Output is correct
6 Correct 1032 ms 86492 KB Output is correct
7 Correct 1108 ms 99196 KB Output is correct
8 Correct 2176 ms 143600 KB Output is correct
9 Correct 1394 ms 99344 KB Output is correct
10 Correct 2326 ms 162820 KB Output is correct
11 Correct 956 ms 58712 KB Output is correct
12 Correct 247 ms 35032 KB Output is correct
13 Incorrect 263 ms 38328 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7748 KB Output is correct
2 Correct 226 ms 16252 KB Output is correct
3 Correct 275 ms 15576 KB Output is correct
4 Correct 299 ms 32276 KB Output is correct
5 Correct 264 ms 30636 KB Output is correct
6 Correct 276 ms 32176 KB Output is correct
7 Correct 182 ms 25140 KB Output is correct
8 Correct 238 ms 34520 KB Output is correct
9 Correct 287 ms 37188 KB Output is correct
10 Correct 211 ms 35140 KB Output is correct
11 Correct 17 ms 8852 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7748 KB Output is correct
2 Correct 226 ms 16252 KB Output is correct
3 Correct 275 ms 15576 KB Output is correct
4 Correct 299 ms 32276 KB Output is correct
5 Correct 264 ms 30636 KB Output is correct
6 Correct 276 ms 32176 KB Output is correct
7 Correct 182 ms 25140 KB Output is correct
8 Correct 238 ms 34520 KB Output is correct
9 Correct 287 ms 37188 KB Output is correct
10 Correct 211 ms 35140 KB Output is correct
11 Correct 17 ms 8852 KB Output is correct
12 Correct 253 ms 18520 KB Output is correct
13 Correct 284 ms 36104 KB Output is correct
14 Correct 286 ms 34472 KB Output is correct
15 Correct 236 ms 35128 KB Output is correct
16 Correct 233 ms 35376 KB Output is correct
17 Correct 262 ms 35288 KB Output is correct
18 Correct 230 ms 35104 KB Output is correct
19 Correct 226 ms 35268 KB Output is correct
20 Correct 171 ms 27744 KB Output is correct
21 Correct 43 ms 17988 KB Output is correct
22 Correct 204 ms 32416 KB Output is correct
23 Correct 233 ms 33168 KB Output is correct
24 Correct 232 ms 33604 KB Output is correct
25 Correct 209 ms 32648 KB Output is correct
26 Correct 246 ms 34244 KB Output is correct
27 Correct 259 ms 35040 KB Output is correct
28 Correct 270 ms 35908 KB Output is correct
29 Correct 311 ms 35876 KB Output is correct
30 Correct 161 ms 27956 KB Output is correct
31 Correct 282 ms 37288 KB Output is correct
32 Correct 213 ms 33348 KB Output is correct
33 Incorrect 221 ms 36152 KB Output isn't correct
34 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 360 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 420 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 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 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1668 ms 112596 KB Output is correct
21 Correct 1676 ms 116632 KB Output is correct
22 Correct 1132 ms 99156 KB Output is correct
23 Correct 1032 ms 86492 KB Output is correct
24 Correct 1108 ms 99196 KB Output is correct
25 Correct 2176 ms 143600 KB Output is correct
26 Correct 1394 ms 99344 KB Output is correct
27 Correct 2326 ms 162820 KB Output is correct
28 Correct 956 ms 58712 KB Output is correct
29 Correct 247 ms 35032 KB Output is correct
30 Incorrect 263 ms 38328 KB Output isn't correct
31 Halted 0 ms 0 KB -