oj.uz

답안 #400453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400453 2021-05-08T05:12:26 Z KoD 새 집 (APIO18_new_home) C++17
80 / 100
 5000 ms 216300 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> 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>;

constexpr i32 MAX = 200000000;

struct Monoid {
    i32 min;
    static Monoid zero() { return Monoid{MAX}; }
    Monoid operator+(const Monoid& other) const {
        return Monoid{std::min(min, other.min)};
    }
};

struct GetMinimum {
    std::priority_queue<i32, Vec<i32>, std::greater<i32>> base, other;
    GetMinimum() : base(), other() {}
    void add(const i32 x) { base.push(x); }
    void remove(const i32 x) { other.push(x); }
    i32 min() {
        while (!other.empty() and base.top() == other.top()) {
            base.pop();
            other.pop();
        }
        return base.top();
    }
};

void main_() {
    usize N, K, Q;
    std::cin >> N >> K >> Q;
    Vec<i32> X(N), A(N), B(N);
    Vec<usize> T(N);
    Vec<i32> L(Q), Y(Q);
    Vec<i32> time;
    time.reserve(2 * N + Q);
    for (const auto i : rep(0, N)) {
        std::cin >> X[i] >> T[i] >> A[i] >> B[i];
        X[i] *= 2;
        T[i] -= 1;
        time.push_back(A[i]);
        time.push_back(B[i]);
    }
    for (const auto i : rep(0, Q)) {
        std::cin >> L[i] >> Y[i];
        L[i] *= 2;
        time.push_back(Y[i]);
    }
    std::sort(time.begin(), time.end());
    time.erase(std::unique(time.begin(), time.end()), time.end());
    const auto Ts = time.size();
    Vec<Vec<usize>> add(Ts), remove(Ts), query(Ts);
    for (const auto i : rep(0, N)) {
        add[std::lower_bound(time.begin(), time.end(), A[i]) - time.begin()]
            .push_back(i);
        remove[std::lower_bound(time.begin(), time.end(), B[i]) - time.begin()]
            .push_back(i);
    }
    for (const auto i : rep(0, Q)) {
        query[std::lower_bound(time.begin(), time.end(), Y[i]) - time.begin()]
            .push_back(i);
    }
    Vec<i32> ans(Q);
    const auto solve = [&] {
        Vec<i32> coord = L;
        std::sort(coord.begin(), coord.end());
        coord.erase(std::unique(coord.begin(), coord.end()), coord.end());
        const auto Xs = coord.size();
        SegmentTree<Monoid> seg(Xs);
        Vec<GetMinimum> lines(Xs);
        Vec<std::multiset<i32>> pts(K);
        const auto add_line = [&](const i32 x, const i32 y) {
            usize i =
                std::upper_bound(coord.begin(), coord.end(), x) - coord.begin();
            if (i == 0) return;
            i -= 1;
            lines[i].add(y);
            seg.assign(i, Monoid{lines[i].min()});
        };
        const auto remove_line = [&](const i32 x, const i32 y) {
            usize i =
                std::upper_bound(coord.begin(), coord.end(), x) - coord.begin();
            if (i == 0) return;
            i -= 1;
            lines[i].remove(y);
            seg.assign(i, Monoid{lines[i].min()});
        };
        for (const auto i : rep(0, Xs)) {
            lines[i].add(MAX);
        }
        for (const auto i : rep(0, K)) {
            pts[i].insert(2 * MAX);
            pts[i].insert(-MAX);
            add_line(MAX / 2, -MAX);
        }
        for (const auto t : rep(0, Ts)) {
            for (const auto i : add[t]) {
                const auto itr = pts[T[i]].lower_bound(X[i]);
                const auto l = *std::prev(itr);
                const auto r = *itr;
                remove_line((l + r) / 2, l);
                add_line((l + X[i]) / 2, l);
                add_line((X[i] + r) / 2, X[i]);
                pts[T[i]].insert(X[i]);
            }
            for (const auto i : query[t]) {
                setmax(ans[i],
                       L[i] - seg.fold(std::lower_bound(coord.begin(),
                                                        coord.end(), L[i]) -
                                           coord.begin(),
                                       Xs)
                                  .min);
            }
            for (const auto i : remove[t]) {
                const auto itr = pts[T[i]].find(X[i]);
                const auto l = *std::prev(itr);
                const auto r = *std::next(itr);
                remove_line((l + X[i]) / 2, l);
                remove_line((X[i] + r) / 2, X[i]);
                add_line((l + r) / 2, l);
                pts[T[i]].erase(itr);
            }
        }
    };
    solve();
    for (auto& x : X) {
        x = MAX - x;
    }
    for (auto& x : L) {
        x = MAX - x;
    }
    solve();
    for (const auto x : ans) {
        std::cout << (x >= MAX ? -1 : x / 2) << '\n';
    }
}

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 3 ms 432 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 3 ms 460 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 3 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 1 ms 332 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 3 ms 460 KB Output is correct
26 Correct 2 ms 464 KB Output is correct
27 Correct 2 ms 332 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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 3 ms 432 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 3 ms 460 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 3 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 1 ms 332 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 3 ms 460 KB Output is correct
26 Correct 2 ms 464 KB Output is correct
27 Correct 2 ms 332 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 707 ms 32088 KB Output is correct
32 Correct 161 ms 6128 KB Output is correct
33 Correct 602 ms 30180 KB Output is correct
34 Correct 610 ms 30412 KB Output is correct
35 Correct 691 ms 32052 KB Output is correct
36 Correct 652 ms 31944 KB Output is correct
37 Correct 419 ms 29644 KB Output is correct
38 Correct 427 ms 29624 KB Output is correct
39 Correct 349 ms 29368 KB Output is correct
40 Correct 365 ms 29464 KB Output is correct
41 Correct 400 ms 29524 KB Output is correct
42 Correct 411 ms 29372 KB Output is correct
43 Correct 79 ms 7660 KB Output is correct
44 Correct 414 ms 29680 KB Output is correct
45 Correct 384 ms 29580 KB Output is correct
46 Correct 364 ms 29212 KB Output is correct
47 Correct 246 ms 28084 KB Output is correct
48 Correct 243 ms 28196 KB Output is correct
49 Correct 273 ms 28468 KB Output is correct
50 Correct 298 ms 28708 KB Output is correct
51 Correct 284 ms 28608 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2977 ms 112544 KB Output is correct
2 Correct 4029 ms 102724 KB Output is correct
3 Correct 1888 ms 143224 KB Output is correct
4 Correct 2663 ms 117376 KB Output is correct
5 Correct 3710 ms 102144 KB Output is correct
6 Correct 3861 ms 102604 KB Output is correct
7 Correct 1577 ms 143332 KB Output is correct
8 Correct 2093 ms 116976 KB Output is correct
9 Correct 2517 ms 107784 KB Output is correct
10 Correct 3017 ms 103516 KB Output is correct
11 Correct 1668 ms 102364 KB Output is correct
12 Correct 1793 ms 103244 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4427 ms 132936 KB Output is correct
2 Correct 950 ms 41204 KB Output is correct
3 Correct 4607 ms 143284 KB Output is correct
4 Correct 2438 ms 186336 KB Output is correct
5 Correct 3529 ms 152124 KB Output is correct
6 Correct 3244 ms 156932 KB Output is correct
7 Correct 4373 ms 142540 KB Output is correct
8 Correct 4570 ms 143040 KB Output is correct
9 Correct 2238 ms 187472 KB Output is correct
10 Correct 3044 ms 155520 KB Output is correct
11 Correct 3650 ms 147776 KB Output is correct
12 Correct 3986 ms 144088 KB Output is correct
13 Correct 1744 ms 141020 KB Output is correct
14 Correct 1713 ms 139648 KB Output is correct
15 Correct 1916 ms 141816 KB Output is correct
16 Correct 2126 ms 143692 KB Output is correct
17 Correct 2016 ms 141484 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 3 ms 432 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 3 ms 460 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 3 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 1 ms 332 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 3 ms 460 KB Output is correct
26 Correct 2 ms 464 KB Output is correct
27 Correct 2 ms 332 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 707 ms 32088 KB Output is correct
32 Correct 161 ms 6128 KB Output is correct
33 Correct 602 ms 30180 KB Output is correct
34 Correct 610 ms 30412 KB Output is correct
35 Correct 691 ms 32052 KB Output is correct
36 Correct 652 ms 31944 KB Output is correct
37 Correct 419 ms 29644 KB Output is correct
38 Correct 427 ms 29624 KB Output is correct
39 Correct 349 ms 29368 KB Output is correct
40 Correct 365 ms 29464 KB Output is correct
41 Correct 400 ms 29524 KB Output is correct
42 Correct 411 ms 29372 KB Output is correct
43 Correct 79 ms 7660 KB Output is correct
44 Correct 414 ms 29680 KB Output is correct
45 Correct 384 ms 29580 KB Output is correct
46 Correct 364 ms 29212 KB Output is correct
47 Correct 246 ms 28084 KB Output is correct
48 Correct 243 ms 28196 KB Output is correct
49 Correct 273 ms 28468 KB Output is correct
50 Correct 298 ms 28708 KB Output is correct
51 Correct 284 ms 28608 KB Output is correct
52 Correct 451 ms 39944 KB Output is correct
53 Correct 440 ms 38272 KB Output is correct
54 Correct 537 ms 34608 KB Output is correct
55 Correct 395 ms 33260 KB Output is correct
56 Correct 388 ms 34928 KB Output is correct
57 Correct 399 ms 30588 KB Output is correct
58 Correct 420 ms 33200 KB Output is correct
59 Correct 428 ms 34964 KB Output is correct
60 Correct 423 ms 30520 KB Output is correct
61 Correct 95 ms 16508 KB Output is correct
62 Correct 435 ms 40184 KB Output is correct
63 Correct 494 ms 35572 KB Output is correct
64 Correct 487 ms 33864 KB Output is correct
65 Correct 481 ms 30948 KB Output is correct
66 Correct 420 ms 29700 KB Output is correct
67 Correct 156 ms 7880 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 3 ms 432 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 3 ms 460 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 3 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 1 ms 332 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 3 ms 460 KB Output is correct
26 Correct 2 ms 464 KB Output is correct
27 Correct 2 ms 332 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 707 ms 32088 KB Output is correct
32 Correct 161 ms 6128 KB Output is correct
33 Correct 602 ms 30180 KB Output is correct
34 Correct 610 ms 30412 KB Output is correct
35 Correct 691 ms 32052 KB Output is correct
36 Correct 652 ms 31944 KB Output is correct
37 Correct 419 ms 29644 KB Output is correct
38 Correct 427 ms 29624 KB Output is correct
39 Correct 349 ms 29368 KB Output is correct
40 Correct 365 ms 29464 KB Output is correct
41 Correct 400 ms 29524 KB Output is correct
42 Correct 411 ms 29372 KB Output is correct
43 Correct 79 ms 7660 KB Output is correct
44 Correct 414 ms 29680 KB Output is correct
45 Correct 384 ms 29580 KB Output is correct
46 Correct 364 ms 29212 KB Output is correct
47 Correct 246 ms 28084 KB Output is correct
48 Correct 243 ms 28196 KB Output is correct
49 Correct 273 ms 28468 KB Output is correct
50 Correct 298 ms 28708 KB Output is correct
51 Correct 284 ms 28608 KB Output is correct
52 Correct 2977 ms 112544 KB Output is correct
53 Correct 4029 ms 102724 KB Output is correct
54 Correct 1888 ms 143224 KB Output is correct
55 Correct 2663 ms 117376 KB Output is correct
56 Correct 3710 ms 102144 KB Output is correct
57 Correct 3861 ms 102604 KB Output is correct
58 Correct 1577 ms 143332 KB Output is correct
59 Correct 2093 ms 116976 KB Output is correct
60 Correct 2517 ms 107784 KB Output is correct
61 Correct 3017 ms 103516 KB Output is correct
62 Correct 1668 ms 102364 KB Output is correct
63 Correct 1793 ms 103244 KB Output is correct
64 Correct 4427 ms 132936 KB Output is correct
65 Correct 950 ms 41204 KB Output is correct
66 Correct 4607 ms 143284 KB Output is correct
67 Correct 2438 ms 186336 KB Output is correct
68 Correct 3529 ms 152124 KB Output is correct
69 Correct 3244 ms 156932 KB Output is correct
70 Correct 4373 ms 142540 KB Output is correct
71 Correct 4570 ms 143040 KB Output is correct
72 Correct 2238 ms 187472 KB Output is correct
73 Correct 3044 ms 155520 KB Output is correct
74 Correct 3650 ms 147776 KB Output is correct
75 Correct 3986 ms 144088 KB Output is correct
76 Correct 1744 ms 141020 KB Output is correct
77 Correct 1713 ms 139648 KB Output is correct
78 Correct 1916 ms 141816 KB Output is correct
79 Correct 2126 ms 143692 KB Output is correct
80 Correct 2016 ms 141484 KB Output is correct
81 Correct 451 ms 39944 KB Output is correct
82 Correct 440 ms 38272 KB Output is correct
83 Correct 537 ms 34608 KB Output is correct
84 Correct 395 ms 33260 KB Output is correct
85 Correct 388 ms 34928 KB Output is correct
86 Correct 399 ms 30588 KB Output is correct
87 Correct 420 ms 33200 KB Output is correct
88 Correct 428 ms 34964 KB Output is correct
89 Correct 423 ms 30520 KB Output is correct
90 Correct 95 ms 16508 KB Output is correct
91 Correct 435 ms 40184 KB Output is correct
92 Correct 494 ms 35572 KB Output is correct
93 Correct 487 ms 33864 KB Output is correct
94 Correct 481 ms 30948 KB Output is correct
95 Correct 420 ms 29700 KB Output is correct
96 Correct 156 ms 7880 KB Output is correct
97 Correct 2841 ms 216300 KB Output is correct
98 Correct 965 ms 35080 KB Output is correct
99 Correct 4819 ms 164948 KB Output is correct
100 Correct 2786 ms 208208 KB Output is correct
101 Correct 3675 ms 187000 KB Output is correct
102 Execution timed out 5040 ms 173388 KB Time limit exceeded
103 Halted 0 ms 0 KB -