oj.uz

Submission #402673

# Submission time Handle Problem Language Result Execution time Memory
402673 2021-05-12T08:31:53 Z KoD Bulldozer (JOI17_bulldozer) C++17
100 / 100
 681 ms 94436 KB 
#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

template <class T, T Div = 2> constexpr T INFTY = std::numeric_limits<T>::max() / Div;

template <class T> bool setmax(T& lhs, const T& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

class revrep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { --itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr revrep(const usize first, const usize last) noexcept
        : first(last - 1), last(std::min(first, last) - 1) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr u64 ceil_log2(const u64 x) {
    u64 e = 0;
    while (((u64)1 << e) < x) ++e;
    return e;
}

template <class Monoid> class SegmentTree {
    using M = Monoid;
    usize internal_size, seg_size;
    std::vector<M> data;

    void fetch(const usize k) { data[k] = data[2 * k] + data[2 * k + 1]; }

  public:
    explicit SegmentTree(const usize size = 0, const M& value = M::zero()) : SegmentTree(std::vector<M>(size, value)) {}
    explicit SegmentTree(const std::vector<M>& vec) : internal_size(vec.size()) {
        seg_size = 1 << ceil_log2(internal_size);
        data = std::vector<M>(2 * seg_size, M::zero());
        for (const usize i : rep(0, internal_size)) data[seg_size + i] = vec[i];
        for (const usize i : revrep(1, seg_size)) fetch(i);
    }

    usize size() const { return internal_size; }

    void assign(usize i, const M& value) {
        assert(i < internal_size);
        i += seg_size;
        data[i] = value;
        while (i > 1) {
            i >>= 1;
            fetch(i);
        }
    }

    M fold() const { return data[1]; }
    M fold(usize l, usize r) const {
        assert(l <= r and r <= internal_size);
        l += seg_size;
        r += seg_size;
        M ret_l = M::zero(), ret_r = M::zero();
        while (l < r) {
            if (l & 1) ret_l = ret_l + data[l++];
            if (r & 1) ret_r = data[--r] + ret_r;
            l >>= 1;
            r >>= 1;
        }
        return ret_l + ret_r;
    }

    template <class F> usize max_right(usize l, const F& f) const {
        assert(l <= internal_size);
        assert(f(M::zero()));
        if (l == internal_size) return internal_size;
        l += seg_size;
        M sum = M::zero();
        do {
            while (!(l & 1)) l >>= 1;
            if (!f(sum + data[l])) {
                while (l < seg_size) {
                    l = 2 * l;
                    if (f(sum + data[l])) sum = sum + data[l++];
                }
                return l - seg_size;
            }
            sum = sum + data[l++];
        } while ((l & -l) != l);
        return internal_size;
    }

    template <class F> usize min_left(usize r, const F& f) const {
        assert(r <= internal_size);
        assert(f(M::zero()));
        if (r == 0) return 0;
        r += seg_size;
        M sum = M::zero();
        do {
            r -= 1;
            while (r > 1 and (r & 1)) r >>= 1;
            if (!f(data[r] + sum)) {
                while (r < seg_size) {
                    r = 2 * r + 1;
                    if (f(data[r] + sum)) sum = data[r--] + sum;
                }
                return r + 1 - seg_size;
            }
            sum = data[r] + sum;
        } while ((r & -r) != r);
        return 0;
    }
};

template <class T> using Vec = std::vector<T>;

struct Query {
    i64 x, y;
    usize i, j;
    bool operator<(const Query& other) const { return (x * other.y) - (y * other.x) > 0; }
};

struct Monoid {
    i64 min, max, dif;
    Monoid(const i64 min, const i64 max, const i64 dif) : min(min), max(max), dif(dif) {}
    Monoid(const i64 val = 0) : min(val), max(val), dif(0) {}
    static Monoid zero() { return Monoid(INFTY<i64>, -INFTY<i64>, -INFTY<i64>); }
    Monoid operator+(const Monoid& other) const {
        return Monoid(std::min(min, other.min), std::max(max, other.max), std::max({dif, other.dif, other.max - min}));
    }
};

void JOI17_bulldozer_main() {
    usize N;
    std::cin >> N;
    Vec<i64> X(N), Y(N), W(N);
    for (const auto i : rep(0, N)) {
        std::cin >> X[i] >> Y[i] >> W[i];
    }
    Vec<usize> order(N);
    std::iota(order.begin(), order.end(), (usize)0);
    std::sort(order.begin(), order.end(),
              [&](const usize i, const usize j) { return X[i] < X[j] or (X[i] == X[j] and Y[i] < Y[j]); });
    Vec<Query> swap;
    swap.reserve(N * (N - 1) / 2);
    for (const auto i : order) {
        for (const auto j : order) {
            if (i == j) {
                continue;
            }
            const auto x = Y[i] - Y[j];
            const auto y = X[j] - X[i];
            if (y < 0 or (x > 0 and y == 0)) {
                continue;
            }
            swap.push_back(Query{x, y, i, j});
        }
    }
    std::stable_sort(swap.begin(), swap.end());
    Vec<i64> sum(N + 1);
    Vec<Monoid> mnd(N + 1);
    Vec<usize> inv(N);
    for (const auto i : rep(0, N)) {
        const auto k = order[i];
        sum[i + 1] = sum[i] + W[k];
        mnd[i + 1] = Monoid(sum[i + 1]);
        inv[k] = i;
    }
    SegmentTree<Monoid> seg(mnd);
    i64 ans = -INFTY<i64>;
    Query last{1, 0, 0, 0};
    for (const auto& dir : swap) {
        if (last < dir) {
            last = dir;
            setmax(ans, seg.fold().dif);
        }
        auto i = dir.i, j = dir.j;
        if (inv[i] > inv[j]) {
            std::swap(i, j);
        }
        const auto l = inv[i];
        const auto r = inv[j];
        assert(l + 1 == r);
        sum[l + 1] = sum[l] + W[j];
        sum[r + 1] = sum[l + 1] + W[i];
        seg.assign(l + 1, Monoid(sum[l + 1]));
        seg.assign(r + 1, Monoid(sum[r + 1]));
        inv[i] = r;
        inv[j] = l;
    }
    setmax(ans, seg.fold().dif);
    std::cout << ans << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    JOI17_bulldozer_main();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 3 ms 460 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 3 ms 460 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 621 ms 94320 KB Output is correct
34 Correct 630 ms 94272 KB Output is correct
35 Correct 640 ms 94272 KB Output is correct
36 Correct 621 ms 94280 KB Output is correct
37 Correct 627 ms 94288 KB Output is correct
38 Correct 615 ms 94204 KB Output is correct
39 Correct 621 ms 94260 KB Output is correct
40 Correct 616 ms 94276 KB Output is correct
41 Correct 632 ms 94352 KB Output is correct
42 Correct 629 ms 94268 KB Output is correct
43 Correct 607 ms 94256 KB Output is correct
44 Correct 655 ms 94148 KB Output is correct
45 Correct 629 ms 94264 KB Output is correct
46 Correct 629 ms 94324 KB Output is correct
47 Correct 610 ms 94276 KB Output is correct
48 Correct 658 ms 94148 KB Output is correct
49 Correct 607 ms 94276 KB Output is correct
50 Correct 623 ms 94264 KB Output is correct
51 Correct 612 ms 94260 KB Output is correct
52 Correct 623 ms 94268 KB Output is correct
53 Correct 613 ms 94276 KB Output is correct
54 Correct 614 ms 94260 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 3 ms 460 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 621 ms 94320 KB Output is correct
34 Correct 630 ms 94272 KB Output is correct
35 Correct 640 ms 94272 KB Output is correct
36 Correct 621 ms 94280 KB Output is correct
37 Correct 627 ms 94288 KB Output is correct
38 Correct 615 ms 94204 KB Output is correct
39 Correct 621 ms 94260 KB Output is correct
40 Correct 616 ms 94276 KB Output is correct
41 Correct 632 ms 94352 KB Output is correct
42 Correct 629 ms 94268 KB Output is correct
43 Correct 607 ms 94256 KB Output is correct
44 Correct 655 ms 94148 KB Output is correct
45 Correct 629 ms 94264 KB Output is correct
46 Correct 629 ms 94324 KB Output is correct
47 Correct 610 ms 94276 KB Output is correct
48 Correct 658 ms 94148 KB Output is correct
49 Correct 607 ms 94276 KB Output is correct
50 Correct 623 ms 94264 KB Output is correct
51 Correct 612 ms 94260 KB Output is correct
52 Correct 623 ms 94268 KB Output is correct
53 Correct 613 ms 94276 KB Output is correct
54 Correct 614 ms 94260 KB Output is correct
55 Correct 625 ms 94312 KB Output is correct
56 Correct 628 ms 94152 KB Output is correct
57 Correct 627 ms 94276 KB Output is correct
58 Correct 635 ms 94272 KB Output is correct
59 Correct 630 ms 94384 KB Output is correct
60 Correct 622 ms 94260 KB Output is correct
61 Correct 616 ms 94268 KB Output is correct
62 Correct 619 ms 94260 KB Output is correct
63 Correct 617 ms 94144 KB Output is correct
64 Correct 631 ms 94276 KB Output is correct
65 Correct 669 ms 94284 KB Output is correct
66 Correct 619 ms 94376 KB Output is correct
67 Correct 618 ms 94148 KB Output is correct
68 Correct 612 ms 94276 KB Output is correct
69 Correct 613 ms 94264 KB Output is correct
70 Correct 624 ms 94264 KB Output is correct
71 Correct 626 ms 94264 KB Output is correct
72 Correct 615 ms 94148 KB Output is correct
73 Correct 622 ms 94276 KB Output is correct
74 Correct 608 ms 94148 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 2 ms 460 KB Output is correct
37 Correct 2 ms 460 KB Output is correct
38 Correct 2 ms 460 KB Output is correct
39 Correct 2 ms 460 KB Output is correct
40 Correct 2 ms 460 KB Output is correct
41 Correct 2 ms 460 KB Output is correct
42 Correct 3 ms 460 KB Output is correct
43 Correct 2 ms 460 KB Output is correct
44 Correct 2 ms 460 KB Output is correct
45 Correct 2 ms 460 KB Output is correct
46 Correct 2 ms 460 KB Output is correct
47 Correct 2 ms 460 KB Output is correct
48 Correct 621 ms 94320 KB Output is correct
49 Correct 630 ms 94272 KB Output is correct
50 Correct 640 ms 94272 KB Output is correct
51 Correct 621 ms 94280 KB Output is correct
52 Correct 627 ms 94288 KB Output is correct
53 Correct 615 ms 94204 KB Output is correct
54 Correct 621 ms 94260 KB Output is correct
55 Correct 616 ms 94276 KB Output is correct
56 Correct 632 ms 94352 KB Output is correct
57 Correct 629 ms 94268 KB Output is correct
58 Correct 607 ms 94256 KB Output is correct
59 Correct 655 ms 94148 KB Output is correct
60 Correct 629 ms 94264 KB Output is correct
61 Correct 629 ms 94324 KB Output is correct
62 Correct 610 ms 94276 KB Output is correct
63 Correct 658 ms 94148 KB Output is correct
64 Correct 607 ms 94276 KB Output is correct
65 Correct 623 ms 94264 KB Output is correct
66 Correct 612 ms 94260 KB Output is correct
67 Correct 623 ms 94268 KB Output is correct
68 Correct 613 ms 94276 KB Output is correct
69 Correct 614 ms 94260 KB Output is correct
70 Correct 625 ms 94312 KB Output is correct
71 Correct 628 ms 94152 KB Output is correct
72 Correct 627 ms 94276 KB Output is correct
73 Correct 635 ms 94272 KB Output is correct
74 Correct 630 ms 94384 KB Output is correct
75 Correct 622 ms 94260 KB Output is correct
76 Correct 616 ms 94268 KB Output is correct
77 Correct 619 ms 94260 KB Output is correct
78 Correct 617 ms 94144 KB Output is correct
79 Correct 631 ms 94276 KB Output is correct
80 Correct 669 ms 94284 KB Output is correct
81 Correct 619 ms 94376 KB Output is correct
82 Correct 618 ms 94148 KB Output is correct
83 Correct 612 ms 94276 KB Output is correct
84 Correct 613 ms 94264 KB Output is correct
85 Correct 624 ms 94264 KB Output is correct
86 Correct 626 ms 94264 KB Output is correct
87 Correct 615 ms 94148 KB Output is correct
88 Correct 622 ms 94276 KB Output is correct
89 Correct 608 ms 94148 KB Output is correct
90 Correct 625 ms 94328 KB Output is correct
91 Correct 643 ms 94340 KB Output is correct
92 Correct 627 ms 94256 KB Output is correct
93 Correct 616 ms 94404 KB Output is correct
94 Correct 612 ms 94320 KB Output is correct
95 Correct 609 ms 94276 KB Output is correct
96 Correct 614 ms 94436 KB Output is correct
97 Correct 641 ms 94324 KB Output is correct
98 Correct 615 ms 94360 KB Output is correct
99 Correct 625 ms 94376 KB Output is correct
100 Correct 549 ms 94368 KB Output is correct
101 Correct 542 ms 94312 KB Output is correct
102 Correct 534 ms 94312 KB Output is correct
103 Correct 574 ms 94304 KB Output is correct
104 Correct 535 ms 94312 KB Output is correct
105 Correct 577 ms 94284 KB Output is correct
106 Correct 560 ms 94384 KB Output is correct
107 Correct 572 ms 94276 KB Output is correct
108 Correct 556 ms 94276 KB Output is correct
109 Correct 572 ms 94268 KB Output is correct
110 Correct 527 ms 94276 KB Output is correct
111 Correct 582 ms 94276 KB Output is correct
112 Correct 532 ms 94396 KB Output is correct
113 Correct 534 ms 94300 KB Output is correct
114 Correct 526 ms 94276 KB Output is correct
115 Correct 555 ms 94300 KB Output is correct
116 Correct 532 ms 94304 KB Output is correct
117 Correct 542 ms 94300 KB Output is correct
118 Correct 551 ms 94276 KB Output is correct
119 Correct 534 ms 94308 KB Output is correct
120 Correct 1 ms 204 KB Output is correct
121 Correct 1 ms 204 KB Output is correct
122 Correct 612 ms 94328 KB Output is correct
123 Correct 616 ms 94328 KB Output is correct
124 Correct 681 ms 94396 KB Output is correct
125 Correct 661 ms 94340 KB Output is correct
126 Correct 654 ms 94328 KB Output is correct
127 Correct 620 ms 94392 KB Output is correct
128 Correct 623 ms 94352 KB Output is correct
129 Correct 627 ms 94324 KB Output is correct
130 Correct 653 ms 94404 KB Output is correct
131 Correct 615 ms 94268 KB Output is correct
132 Correct 608 ms 94208 KB Output is correct
133 Correct 617 ms 94332 KB Output is correct