oj.uz

Submission #1076180

# Submission time Handle Problem Language Result Execution time Memory
1076180 2024-08-26T11:37:31 Z j_vdd16 Sky Walking (IOI19_walk) C++17
15 / 100
 148 ms 26464 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));

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

    sort(all(ys));

    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));
            
            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) {
                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 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 41 ms 8156 KB Output is correct
2 Correct 91 ms 13792 KB Output is correct
3 Correct 116 ms 15172 KB Output is correct
4 Correct 131 ms 22188 KB Output is correct
5 Correct 120 ms 22096 KB Output is correct
6 Correct 129 ms 22076 KB Output is correct
7 Correct 78 ms 15552 KB Output is correct
8 Correct 133 ms 23104 KB Output is correct
9 Correct 122 ms 22332 KB Output is correct
10 Correct 95 ms 22196 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 41 ms 8156 KB Output is correct
2 Correct 91 ms 13792 KB Output is correct
3 Correct 116 ms 15172 KB Output is correct
4 Correct 131 ms 22188 KB Output is correct
5 Correct 120 ms 22096 KB Output is correct
6 Correct 129 ms 22076 KB Output is correct
7 Correct 78 ms 15552 KB Output is correct
8 Correct 133 ms 23104 KB Output is correct
9 Correct 122 ms 22332 KB Output is correct
10 Correct 95 ms 22196 KB Output is correct
11 Correct 10 ms 4188 KB Output is correct
12 Correct 102 ms 17220 KB Output is correct
13 Correct 148 ms 26160 KB Output is correct
14 Correct 140 ms 26300 KB Output is correct
15 Correct 113 ms 26184 KB Output is correct
16 Correct 124 ms 26436 KB Output is correct
17 Correct 130 ms 26464 KB Output is correct
18 Correct 112 ms 26144 KB Output is correct
19 Correct 130 ms 26436 KB Output is correct
20 Correct 82 ms 18600 KB Output is correct
21 Correct 24 ms 10320 KB Output is correct
22 Correct 131 ms 24256 KB Output is correct
23 Correct 112 ms 24732 KB Output is correct
24 Correct 118 ms 24976 KB Output is correct
25 Correct 116 ms 24252 KB Output is correct
26 Correct 129 ms 24976 KB Output is correct
27 Correct 138 ms 26176 KB Output is correct
28 Correct 148 ms 26176 KB Output is correct
29 Correct 145 ms 26176 KB Output is correct
30 Correct 82 ms 18976 KB Output is correct
31 Correct 128 ms 26428 KB Output is correct
32 Correct 102 ms 25048 KB Output is correct
33 Incorrect 101 ms 26088 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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