oj.uz

Submission #1076195

# Submission time Handle Problem Language Result Execution time Memory
1076195 2024-08-26T11:41:59 Z j_vdd16 Sky Walking (IOI19_walk) C++17
15 / 100
 171 ms 23104 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 || newCost >= LLONG_MAX / 2) {
                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 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 92 ms 13588 KB Output is correct
3 Correct 110 ms 15164 KB Output is correct
4 Correct 128 ms 22340 KB Output is correct
5 Correct 158 ms 22196 KB Output is correct
6 Correct 122 ms 22084 KB Output is correct
7 Correct 72 ms 15740 KB Output is correct
8 Correct 162 ms 23104 KB Output is correct
9 Correct 118 ms 22336 KB Output is correct
10 Correct 98 ms 22352 KB Output is correct
11 Correct 8 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 92 ms 13588 KB Output is correct
3 Correct 110 ms 15164 KB Output is correct
4 Correct 128 ms 22340 KB Output is correct
5 Correct 158 ms 22196 KB Output is correct
6 Correct 122 ms 22084 KB Output is correct
7 Correct 72 ms 15740 KB Output is correct
8 Correct 162 ms 23104 KB Output is correct
9 Correct 118 ms 22336 KB Output is correct
10 Correct 98 ms 22352 KB Output is correct
11 Correct 8 ms 4188 KB Output is correct
12 Correct 103 ms 15172 KB Output is correct
13 Correct 107 ms 22336 KB Output is correct
14 Correct 171 ms 22456 KB Output is correct
15 Correct 108 ms 22312 KB Output is correct
16 Correct 126 ms 22348 KB Output is correct
17 Correct 123 ms 22340 KB Output is correct
18 Correct 124 ms 22292 KB Output is correct
19 Correct 134 ms 22336 KB Output is correct
20 Correct 84 ms 15524 KB Output is correct
21 Incorrect 36 ms 8136 KB Output isn't correct
22 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 -