oj.uz

Submission #1076190

# Submission time Handle Problem Language Result Execution time Memory
1076190 2024-08-26T11:41:21 Z j_vdd16 Sky Walking (IOI19_walk) C++17
15 / 100
 186 ms 23220 KB 
#include "walk.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

struct SegTree {
    int n, N;
    vi tree;
    int def = LLONG_MAX / 2;

    SegTree(vi values) {
        n = values.size();
        N = 1;
        while (N < n) N *= 2;

        tree = vi(2 * N, def);
        loop(i, n) {
            tree[N + i] = values[i];
        }

        for (int i = N - 1; i >= 1; i--) {
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
        }
    }

    int merge(int a, int b) {
        return min(a, b);
    }

    void set(int idx, int v) {
        idx += N;
        tree[idx] = v;
        idx /= 2;

        while (idx) {
            tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
            idx /= 2;
        }
    }

    int get(int l, int r, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) {
            tr = N;
        }

        if (tr <= l || tl >= r) {
            return def;
        }

        if (tl >= l && tr <= r) {
            return tree[i];
        }

        int tm = (tl + tr) / 2;
        return merge(get(l, r, i * 2, tl, tm), get(l, r, i * 2 + 1, tm, tr));
    }
};

long long min_distance(std::vector<signed> xs, std::vector<signed> hs, std::vector<signed> ls, std::vector<signed> rs, std::vector<signed> ys, signed s, signed g) {
    int n = xs.size();
    int m = ls.size();

    vector<tuple<int, int, int>> bridges(m);
    loop(i, m) {
        bridges[i] = { ys[i], ls[i], rs[i] };
    }
    sort(all(bridges));
    sort(all(ys));

    vii buildings(n);
    loop(i, n) {
        buildings[i] = { xs[i], hs[i] };
    }
    sort(all(buildings));


    SegTree minCost(vi(m, LLONG_MAX / 2));
    SegTree minCostMinusHeight(vi(m, LLONG_MAX / 2));

    vvii open(n), close(n);
    loop(i, m) {
        auto [y, l, r] = bridges[i];

        open[l].push_back({y, i});
        close[r].push_back({y, i});
    }
    loop(i, n) {
        sort(all(open[i]));
        sort(all(close[i]));
    }

    for (auto [y, j] : open[0]) {
        minCost.set(j, ys[j]);
        minCostMinusHeight.set(j, 0);
    }
    for (int i = 1; i < n; i++) {
        int upper = upper_bound(all(ys), buildings[i].second) - ys.begin();
        for (auto [y, j] : open[i]) {
            int newCost = min(minCostMinusHeight.get(0, j) + y, minCost.get(j + 1, upper));
            if (newCost < 0) {
                return -1;
            }
            
            minCost.set(j, newCost);
            minCostMinusHeight.set(j, newCost - y);
        }

        if (i == n - 1) {
	        int res = minCost.get(0, m) * 2LL + (int64_t)xs[g] - (int64_t)xs[s];
            if (res < 0 || res >= LLONG_MAX / 2) {
                return -1;
            }
            return res;
        }

        for (auto [y, j] : close[i]) {
            minCost.set(j, LLONG_MAX / 2);
            minCostMinusHeight.set(j, LLONG_MAX / 2);
        }
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8208 KB Output is correct
2 Correct 87 ms 13644 KB Output is correct
3 Correct 99 ms 15180 KB Output is correct
4 Correct 127 ms 22356 KB Output is correct
5 Correct 122 ms 22080 KB Output is correct
6 Correct 135 ms 22080 KB Output is correct
7 Correct 78 ms 15672 KB Output is correct
8 Correct 186 ms 23220 KB Output is correct
9 Correct 148 ms 22336 KB Output is correct
10 Correct 108 ms 22336 KB Output is correct
11 Correct 10 ms 4188 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8208 KB Output is correct
2 Correct 87 ms 13644 KB Output is correct
3 Correct 99 ms 15180 KB Output is correct
4 Correct 127 ms 22356 KB Output is correct
5 Correct 122 ms 22080 KB Output is correct
6 Correct 135 ms 22080 KB Output is correct
7 Correct 78 ms 15672 KB Output is correct
8 Correct 186 ms 23220 KB Output is correct
9 Correct 148 ms 22336 KB Output is correct
10 Correct 108 ms 22336 KB Output is correct
11 Correct 10 ms 4188 KB Output is correct
12 Correct 101 ms 15180 KB Output is correct
13 Correct 160 ms 22380 KB Output is correct
14 Correct 171 ms 22228 KB Output is correct
15 Correct 121 ms 22352 KB Output is correct
16 Correct 142 ms 22292 KB Output is correct
17 Correct 159 ms 22332 KB Output is correct
18 Correct 118 ms 22352 KB Output is correct
19 Correct 135 ms 22204 KB Output is correct
20 Correct 91 ms 15564 KB Output is correct
21 Correct 24 ms 8284 KB Output is correct
22 Correct 122 ms 20416 KB Output is correct
23 Correct 122 ms 21008 KB Output is correct
24 Correct 112 ms 21196 KB Output is correct
25 Correct 113 ms 20668 KB Output is correct
26 Correct 114 ms 21144 KB Output is correct
27 Correct 184 ms 22080 KB Output is correct
28 Correct 158 ms 22336 KB Output is correct
29 Correct 175 ms 22080 KB Output is correct
30 Correct 92 ms 15556 KB Output is correct
31 Correct 163 ms 22336 KB Output is correct
32 Correct 131 ms 21724 KB Output is correct
33 Incorrect 108 ms 22848 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -