oj.uz

Submission #761889

# Submission time Handle Problem Language Result Execution time Memory
761889 2023-06-20T11:00:24 Z MinaRagy06 Sky Walking (IOI19_walk) C++17
24 / 100
 707 ms 391364 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SZ(x) (int)x.size()

struct bheap {
    vector<int> heap, mp;
    vector<ll> val;
    bheap() {}
    bheap(int n) {
        val.assign(n, 1e9);
        mp.assign(n, -1);
    }
    void sink(int pos) {
        while ((pos << 1) + 1 < SZ(heap)) {
            int l = (pos << 1) + 1, r = (pos << 1) + 2;
            int smallest = l;
            if (r < SZ(heap) && val[heap[r]] < val[heap[l]]) smallest = r;
            if (val[heap[smallest]] < val[heap[pos]]){
                mp[heap[smallest]] = pos;
                mp[heap[pos]] = smallest;
                swap(heap[pos], heap[smallest]);
            } else {
                break;
            }
            pos = smallest;
        }
    }
    bool swim(int pos) {
        int p = (pos - 1) >> 1;
        if (!(pos && val[heap[p]] > val[heap[pos]])) return 0;
        while (pos && val[heap[p]] > val[heap[pos]]) {
            mp[heap[p]] = pos;
            mp[heap[pos]] = p;
            swap(heap[p], heap[pos]);
            pos = p;
            p = (pos - 1) >> 1;
        }
        return 1;
    }
    void push(int key, ll value) {
        int pos = SZ(heap);
        heap.push_back(key);
        mp[key] = pos;
        val[key] = value;
        swim(pos);
    }
    int pop() {
        int n = SZ(heap), ret = heap[0];
        mp[heap[0]] = n - 1;
        mp[heap[n - 1]] = 0;
        swap(heap[0], heap[n-1]);
        heap.pop_back();
        sink(0);
        return ret;
    }
    void update(int key, ll value) {
        int pos = mp[key];
        val[key] = value;
        if (!swim(pos)) {
            sink(pos);
        }
    }
    int top() {
        return heap[0];
    }
    bool empty() {
        return heap.empty();
    }
};
vector<int> intersect[100'005];
vector<int> adj[2'000'005];
vector<ll> dist[100'005];
vector<int> idx[100'005], mp[100'005];
pair<int, int> rev[2'000'005];
int sparse[17][200'005];
const ll INF = 1e18;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
    l.push_back(0), r.push_back(0), y.push_back(0);
    vector<array<int, 3>> sorted(SZ(y));
    idx[s].push_back(0), dist[s].push_back(INF);
    for (int i = 0; i < SZ(y); i++) {
        sorted[i] = {l[i], r[i], y[i]};
    }
    sort(sorted.begin(), sorted.end(), [&](array<int, 3> _a, array<int, 3> _b) {return _a[2] < _b[2];});
    for (int i = 0; i < SZ(y); i++) {
        l[i] = sorted[i][0], r[i] = sorted[i][1], y[i] = sorted[i][2];
    }
    int n = SZ(x), m = SZ(l) - 1;
    for (int i = 0; i < n; i++) {
        sparse[0][i] = h[i];
    }
    for (int j = 1; j < 17; j++) {
        for (int i = 0; i < n; i++) {
            sparse[j][i] = max(sparse[j - 1][i], sparse[j - 1][i + (1 << (j - 1))]);
        }
    }
    for (int i = 1; i <= m; i++) {
        int j = l[i];
        while (j <= r[i]) {
            if (y[i] <= h[j]) {
                intersect[i].push_back(j);
                j++;
                continue;
            }
            int mx = 0;
            for (int k = 16; k >= 0; k--) {
                if (y[i] > max(mx, sparse[k][j])) {
                    mx = max(mx, sparse[k][j]);
                    j += (1 << k);
                }
            }
            if (j <= r[i]) {
                intersect[i].push_back(j);
                j++;
            }
        }
        for (int k = 0; k < SZ(intersect[i]); k++) {
            dist[intersect[i][k]].push_back(INF);
            idx[intersect[i][k]].push_back(i);
        }
    }
    int cur = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < SZ(idx[i]); j++) {
            rev[cur] = {i, j};
            mp[i].push_back(cur++);
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int k = 0; k < SZ(intersect[i]); k++) {
            int ypos = lower_bound(idx[intersect[i][k]].begin(), idx[intersect[i][k]].end(), i) - idx[intersect[i][k]].begin();
            if (k + 1 < SZ(intersect[i])) {
                int y2pos = lower_bound(idx[intersect[i][k + 1]].begin(), idx[intersect[i][k + 1]].end(), i) - idx[intersect[i][k + 1]].begin();
                int u = mp[intersect[i][k]][ypos];
                int v = mp[intersect[i][k + 1]][y2pos];
                adj[u].push_back(v);
            }
            if (k - 1 >= 0) {
                int y2pos = lower_bound(idx[intersect[i][k - 1]].begin(), idx[intersect[i][k - 1]].end(), i) - idx[intersect[i][k - 1]].begin();
                int u = mp[intersect[i][k]][ypos];
                int v = mp[intersect[i][k - 1]][y2pos];
                adj[u].push_back(v);
            }
        }
    }
    bheap pq(cur);
    pq.push(mp[s][0], 0);
    dist[s][0] = 0;
    while (!pq.empty()) {
        int node = pq.pop();
        int i = rev[node].first;
        int j = rev[node].second;
        ll d = dist[i][j];
        j = y[idx[i][j]];
        if (node - 1 >= 0 && rev[node - 1].first == i) {
            auto [nxt, nxth] = rev[node - 1];
            ll newd = d + abs(j - y[idx[nxt][nxth]]);
            if (dist[nxt][nxth] == INF) {
                dist[nxt][nxth] = newd;
                pq.push(mp[nxt][nxth], newd);
            } else if (newd < dist[nxt][nxth]) {
                dist[nxt][nxth] = newd;
                pq.update(mp[nxt][nxth], newd);
            }
        }
        if (node + 1 < cur && rev[node + 1].first == i) {
            auto [nxt, nxth] = rev[node + 1];
            ll newd = d + abs(j - y[idx[nxt][nxth]]);
            if (dist[nxt][nxth] == INF) {
                dist[nxt][nxth] = newd;
                pq.push(mp[nxt][nxth], newd);
            } else if (newd < dist[nxt][nxth]) {
                dist[nxt][nxth] = newd;
                pq.update(mp[nxt][nxth], newd);
            }
        }
        for (auto nxtnode : adj[node]) {
            auto [nxt, nxth] = rev[nxtnode];
            ll newd = d + abs(x[nxt] - x[i]) + abs(j - y[idx[nxt][nxth]]);
            if (dist[nxt][nxth] == INF) {
                dist[nxt][nxth] = newd;
                pq.push(mp[nxt][nxth], newd);
            } else if (newd < dist[nxt][nxth]) {
                dist[nxt][nxth] = newd;
                pq.update(mp[nxt][nxth], newd);
            }
        }
    }
    ll ans = INF;
    for (int i = 0; i < SZ(dist[g]); i++) {
        ans = min(ans, dist[g][i] + y[idx[g][i]]);
    }
    if (ans >= INF) return -1;
    return ans;
}
// int main() {
//     ios_base::sync_with_stdio(0), cin.tie(0);
//     int N, M;
//     cin >> N >> M;
//     vector<int> X(N), H(N);
//     for (int i = 0; i < N; i++) {
//         cin >> X[i] >> H[i];
//     }
//     vector<int> L(M), R(M), Y(M);
//     for (int i = 0; i < M; i++) {
//         cin >> L[i] >> R[i] >> Y[i];
//     }
//     int S, G;
//     cin >> S >> G;
//     cout << min_distance(X, H, L, R, Y, S, G) << '\n';
//     return 0;
// }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56660 KB Output is correct
2 Correct 25 ms 56664 KB Output is correct
3 Correct 28 ms 56652 KB Output is correct
4 Correct 25 ms 56772 KB Output is correct
5 Correct 27 ms 56788 KB Output is correct
6 Correct 26 ms 56764 KB Output is correct
7 Correct 26 ms 56788 KB Output is correct
8 Correct 30 ms 56792 KB Output is correct
9 Correct 25 ms 56660 KB Output is correct
10 Correct 26 ms 56756 KB Output is correct
11 Correct 25 ms 56728 KB Output is correct
12 Correct 26 ms 56704 KB Output is correct
13 Correct 25 ms 56772 KB Output is correct
14 Correct 25 ms 56732 KB Output is correct
15 Correct 25 ms 56740 KB Output is correct
16 Correct 28 ms 56712 KB Output is correct
17 Correct 26 ms 56800 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56660 KB Output is correct
2 Correct 25 ms 56648 KB Output is correct
3 Correct 464 ms 120232 KB Output is correct
4 Correct 476 ms 129540 KB Output is correct
5 Correct 265 ms 120472 KB Output is correct
6 Correct 246 ms 114728 KB Output is correct
7 Correct 271 ms 120652 KB Output is correct
8 Correct 581 ms 135436 KB Output is correct
9 Correct 371 ms 119692 KB Output is correct
10 Correct 707 ms 154676 KB Output is correct
11 Correct 243 ms 95056 KB Output is correct
12 Correct 175 ms 91896 KB Output is correct
13 Correct 575 ms 146208 KB Output is correct
14 Correct 133 ms 90732 KB Output is correct
15 Correct 196 ms 91956 KB Output is correct
16 Correct 175 ms 91444 KB Output is correct
17 Correct 171 ms 90436 KB Output is correct
18 Correct 132 ms 86588 KB Output is correct
19 Correct 33 ms 58644 KB Output is correct
20 Correct 74 ms 75100 KB Output is correct
21 Correct 164 ms 90368 KB Output is correct
22 Correct 178 ms 94288 KB Output is correct
23 Correct 169 ms 97840 KB Output is correct
24 Correct 179 ms 93488 KB Output is correct
25 Correct 170 ms 92400 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 70032 KB Output is correct
2 Runtime error 352 ms 391364 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 70032 KB Output is correct
2 Runtime error 352 ms 391364 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56660 KB Output is correct
2 Correct 25 ms 56664 KB Output is correct
3 Correct 28 ms 56652 KB Output is correct
4 Correct 25 ms 56772 KB Output is correct
5 Correct 27 ms 56788 KB Output is correct
6 Correct 26 ms 56764 KB Output is correct
7 Correct 26 ms 56788 KB Output is correct
8 Correct 30 ms 56792 KB Output is correct
9 Correct 25 ms 56660 KB Output is correct
10 Correct 26 ms 56756 KB Output is correct
11 Correct 25 ms 56728 KB Output is correct
12 Correct 26 ms 56704 KB Output is correct
13 Correct 25 ms 56772 KB Output is correct
14 Correct 25 ms 56732 KB Output is correct
15 Correct 25 ms 56740 KB Output is correct
16 Correct 28 ms 56712 KB Output is correct
17 Correct 26 ms 56800 KB Output is correct
18 Correct 25 ms 56660 KB Output is correct
19 Correct 25 ms 56648 KB Output is correct
20 Correct 464 ms 120232 KB Output is correct
21 Correct 476 ms 129540 KB Output is correct
22 Correct 265 ms 120472 KB Output is correct
23 Correct 246 ms 114728 KB Output is correct
24 Correct 271 ms 120652 KB Output is correct
25 Correct 581 ms 135436 KB Output is correct
26 Correct 371 ms 119692 KB Output is correct
27 Correct 707 ms 154676 KB Output is correct
28 Correct 243 ms 95056 KB Output is correct
29 Correct 175 ms 91896 KB Output is correct
30 Correct 575 ms 146208 KB Output is correct
31 Correct 133 ms 90732 KB Output is correct
32 Correct 196 ms 91956 KB Output is correct
33 Correct 175 ms 91444 KB Output is correct
34 Correct 171 ms 90436 KB Output is correct
35 Correct 132 ms 86588 KB Output is correct
36 Correct 33 ms 58644 KB Output is correct
37 Correct 74 ms 75100 KB Output is correct
38 Correct 164 ms 90368 KB Output is correct
39 Correct 178 ms 94288 KB Output is correct
40 Correct 169 ms 97840 KB Output is correct
41 Correct 179 ms 93488 KB Output is correct
42 Correct 170 ms 92400 KB Output is correct
43 Correct 73 ms 70032 KB Output is correct
44 Runtime error 352 ms 391364 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -