oj.uz

답안 #424574

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
424574 2021-06-12T06:30:15 Z yuto1115 Sky Walking (IOI19_walk) C++17
0 / 100
 2263 ms 162580 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(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]) {
                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 >= 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;
      |                ~~^~~~~~~~~~~~~
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 304 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 268 KB Output is correct
13 Correct 1 ms 296 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1634 ms 112500 KB Output is correct
4 Correct 1614 ms 116380 KB Output is correct
5 Correct 1088 ms 99052 KB Output is correct
6 Correct 910 ms 86424 KB Output is correct
7 Correct 1054 ms 99072 KB Output is correct
8 Correct 2013 ms 143428 KB Output is correct
9 Correct 1368 ms 99176 KB Output is correct
10 Correct 2263 ms 162580 KB Output is correct
11 Correct 819 ms 58476 KB Output is correct
12 Incorrect 238 ms 34948 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 8116 KB Output is correct
2 Correct 248 ms 16360 KB Output is correct
3 Correct 216 ms 17448 KB Output is correct
4 Correct 264 ms 36004 KB Output is correct
5 Correct 254 ms 34432 KB Output is correct
6 Correct 270 ms 36024 KB Output is correct
7 Correct 139 ms 27992 KB Output is correct
8 Incorrect 243 ms 38332 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 8116 KB Output is correct
2 Correct 248 ms 16360 KB Output is correct
3 Correct 216 ms 17448 KB Output is correct
4 Correct 264 ms 36004 KB Output is correct
5 Correct 254 ms 34432 KB Output is correct
6 Correct 270 ms 36024 KB Output is correct
7 Correct 139 ms 27992 KB Output is correct
8 Incorrect 243 ms 38332 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 304 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 268 KB Output is correct
13 Correct 1 ms 296 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 -