oj.uz

Submission #1076166

# Submission time Handle Problem Language Result Execution time Memory
1076166 2024-08-26T11:32:19 Z j_vdd16 Sky Walking (IOI19_walk) C++17
0 / 100
 156 ms 23888 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));
    vi ys64(m);
    loop(i, m) {
        ys64[i] = ys[i];
    }

    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, ys64[j]);
        minCostMinusHeight.set(j, 0);
    }
    for (int i = 1; i < n; i++) {
        int upper = upper_bound(all(ys64), buildings[i].second) - ys64.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) {
	        return minCost.get(0, m) * 2 + xs[g] - xs[s];
        }

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8412 KB Output is correct
2 Correct 87 ms 14404 KB Output is correct
3 Correct 94 ms 15760 KB Output is correct
4 Correct 129 ms 23108 KB Output is correct
5 Correct 119 ms 22836 KB Output is correct
6 Correct 156 ms 22956 KB Output is correct
7 Correct 71 ms 16068 KB Output is correct
8 Correct 144 ms 23888 KB Output is correct
9 Correct 119 ms 23100 KB Output is correct
10 Correct 93 ms 23104 KB Output is correct
11 Incorrect 10 ms 4184 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8412 KB Output is correct
2 Correct 87 ms 14404 KB Output is correct
3 Correct 94 ms 15760 KB Output is correct
4 Correct 129 ms 23108 KB Output is correct
5 Correct 119 ms 22836 KB Output is correct
6 Correct 156 ms 22956 KB Output is correct
7 Correct 71 ms 16068 KB Output is correct
8 Correct 144 ms 23888 KB Output is correct
9 Correct 119 ms 23100 KB Output is correct
10 Correct 93 ms 23104 KB Output is correct
11 Incorrect 10 ms 4184 KB Output isn't correct
12 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 -