oj.uz

Submission #1076198

# Submission time Handle Problem Language Result Execution time Memory
1076198 2024-08-26T11:42:36 Z j_vdd16 Sky Walking (IOI19_walk) C++17
15 / 100
 186 ms 23100 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 upper = upper_bound(all(ys), buildings[i].second) - ys.begin();
	        int res = minCost.get(0, upper) * 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 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8204 KB Output is correct
2 Correct 97 ms 13796 KB Output is correct
3 Correct 110 ms 15188 KB Output is correct
4 Correct 159 ms 22356 KB Output is correct
5 Correct 128 ms 22268 KB Output is correct
6 Correct 141 ms 22196 KB Output is correct
7 Correct 76 ms 15504 KB Output is correct
8 Correct 186 ms 23100 KB Output is correct
9 Correct 138 ms 22340 KB Output is correct
10 Correct 89 ms 22336 KB Output is correct
11 Correct 9 ms 4184 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8204 KB Output is correct
2 Correct 97 ms 13796 KB Output is correct
3 Correct 110 ms 15188 KB Output is correct
4 Correct 159 ms 22356 KB Output is correct
5 Correct 128 ms 22268 KB Output is correct
6 Correct 141 ms 22196 KB Output is correct
7 Correct 76 ms 15504 KB Output is correct
8 Correct 186 ms 23100 KB Output is correct
9 Correct 138 ms 22340 KB Output is correct
10 Correct 89 ms 22336 KB Output is correct
11 Correct 9 ms 4184 KB Output is correct
12 Correct 103 ms 15168 KB Output is correct
13 Correct 71 ms 22340 KB Output is correct
14 Correct 145 ms 22080 KB Output is correct
15 Correct 114 ms 22336 KB Output is correct
16 Correct 130 ms 22336 KB Output is correct
17 Correct 122 ms 22336 KB Output is correct
18 Correct 112 ms 22336 KB Output is correct
19 Correct 124 ms 22364 KB Output is correct
20 Correct 88 ms 15420 KB Output is correct
21 Incorrect 19 ms 8280 KB Output isn't correct
22 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 -