oj.uz

Submission #428388

# Submission time Handle Problem Language Result Execution time Memory
428388 2021-06-15T11:17:47 Z KoD Road Construction (JOI21_road_construction) C++17
100 / 100
 6861 ms 1102428 KB 
#include <bits/stdc++.h>

using ll = long long;
template <class T> using Vec = std::vector<T>;
template <class T> using Rc = std::shared_ptr<const T>;
template <class T> using Heap = std::priority_queue<T, Vec<T>, std::greater<T>>;

constexpr int INF = std::numeric_limits<int>::max();

int scan() {
    int x;
    std::scanf("%d", &x);
    return x;
}

void print(const ll x) {
    std::printf("%lld\n", x);
}

struct Node;
using Ptr = Rc<Node>;

struct Node {
    int left, right;
    std::pair<int, int> value;
    Ptr lch, rch;
    explicit Node(const int i, const int x = -INF) : left(i), right(i + 1), value(x, i), lch(), rch() {}
    explicit Node(const Ptr& l, const Ptr& r) : left(l -> left), right(r -> right), value(std::max(l -> value, r -> value)), lch(l), rch(r) {}
};

Ptr build(const int l, const int r) {
    if (l + 1 == r) return std::make_shared<Node>(l);
    const int m = (l + r) / 2;
    return std::make_shared<Node>(build(l, m), build(m, r));
}

Ptr assign(const Ptr& n, const int i, const int x) {
    if (n -> left == i and n -> right == i + 1) return std::make_shared<Node>(i, x);
    if (i < n -> lch -> right) return std::make_shared<Node>(assign(n -> lch, i, x), n -> rch);
    else return std::make_shared<Node>(n -> lch, assign(n -> rch, i, x));
}

std::pair<int, int> fold(const Ptr& n, const int l, const int r) {
    if (r <= n -> left or n -> right <= l) return {-INF, -INF};
    if (l <= n -> left and n -> right <= r) return n -> value;
    return std::max(fold(n -> lch, l, r), fold(n -> rch, l, r));
}

int main() {
    const int N = scan();
    int K = scan();
    Vec<std::pair<int, int>> Pts(N);
    for (auto& [x, y] : Pts) {
        x = scan();
        y = scan();
    }
    std::sort(Pts.begin(), Pts.end());
    Vec<int> idx(N);
    {
        Vec<std::pair<int, int>> cmp;
        cmp.reserve(N);
        for (int i = 0; i < N; ++i) {
            cmp.emplace_back(Pts[i].second, i);
        }
        std::sort(cmp.begin(), cmp.end());
        for (int i = 0; i < N; ++i) {
            idx[cmp[i].second] = i;
        }
    }
    Vec<Ptr> seg1(N), seg2(N);
    seg1[0] = seg2[0] = build(0, N);
    for (int i = 0; i < N - 1; ++i) {
        seg1[i + 1] = assign(seg1[i], idx[i], (Pts[i].first - Pts[i].second));
        seg2[i + 1] = assign(seg2[i], idx[i], (Pts[i].first + Pts[i].second));
    }
    Heap<std::tuple<ll, int, int>> heap;
    for (int i = 1; i < N; ++i) {
        {
            const auto [x, j] = fold(seg1[i], idx[i], N);
            if (x != -INF) {
                heap.emplace((ll) (Pts[i].first - Pts[i].second) - (ll) x, i, j);
            }
        }
        {
            const auto [x, j] = fold(seg2[i], 0, idx[i]);
            if (x != -INF) {
                heap.emplace((ll) (Pts[i].first + Pts[i].second) - (ll) x, i, j);
            }
        }
    }
    while (K > 0) {
        const auto [x, i, j] = heap.top();
        heap.pop();
        print(x);
        K -= 1;
        if (j >= idx[i]) {
            seg1[i] = assign(seg1[i], j, -INF);
            const auto [x, j] = fold(seg1[i], idx[i], N);
            if (x != -INF) {
                heap.emplace((ll) (Pts[i].first - Pts[i].second) - (ll) x, i, j);
            }
        } else {
            seg2[i] = assign(seg2[i], j, -INF);
            const auto [x, j] = fold(seg2[i], 0, idx[i]);
            if (x != -INF) {
                heap.emplace((ll) (Pts[i].first + Pts[i].second) - (ll) x, i, j);
            }
        }
    }
    return 0;
}

Compilation message

road_construction.cpp: In function 'int scan()':
road_construction.cpp:12:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     std::scanf("%d", &x);
      |     ~~~~~~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 65604 KB Output is correct
2 Correct 1078 ms 65536 KB Output is correct
3 Correct 916 ms 54140 KB Output is correct
4 Correct 801 ms 50660 KB Output is correct
5 Correct 977 ms 53976 KB Output is correct
6 Correct 7 ms 3308 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3383 ms 839152 KB Output is correct
2 Correct 3225 ms 839132 KB Output is correct
3 Correct 440 ms 42832 KB Output is correct
4 Correct 2673 ms 839048 KB Output is correct
5 Correct 2570 ms 839064 KB Output is correct
6 Correct 2539 ms 839168 KB Output is correct
7 Correct 2560 ms 838632 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4006 ms 807280 KB Output is correct
2 Correct 4412 ms 807204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1980 ms 801016 KB Output is correct
5 Correct 2512 ms 807532 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4006 ms 807280 KB Output is correct
2 Correct 4412 ms 807204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1980 ms 801016 KB Output is correct
5 Correct 2512 ms 807532 KB Output is correct
6 Correct 4118 ms 807296 KB Output is correct
7 Correct 4065 ms 807304 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 4212 ms 807244 KB Output is correct
11 Correct 1895 ms 801088 KB Output is correct
12 Correct 2509 ms 807476 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 65604 KB Output is correct
2 Correct 1078 ms 65536 KB Output is correct
3 Correct 916 ms 54140 KB Output is correct
4 Correct 801 ms 50660 KB Output is correct
5 Correct 977 ms 53976 KB Output is correct
6 Correct 7 ms 3308 KB Output is correct
7 Correct 3340 ms 547408 KB Output is correct
8 Correct 3398 ms 547468 KB Output is correct
9 Correct 657 ms 50536 KB Output is correct
10 Correct 2516 ms 354096 KB Output is correct
11 Correct 2808 ms 409076 KB Output is correct
12 Correct 1658 ms 503056 KB Output is correct
13 Correct 1780 ms 469444 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 65604 KB Output is correct
2 Correct 1078 ms 65536 KB Output is correct
3 Correct 916 ms 54140 KB Output is correct
4 Correct 801 ms 50660 KB Output is correct
5 Correct 977 ms 53976 KB Output is correct
6 Correct 7 ms 3308 KB Output is correct
7 Correct 3383 ms 839152 KB Output is correct
8 Correct 3225 ms 839132 KB Output is correct
9 Correct 440 ms 42832 KB Output is correct
10 Correct 2673 ms 839048 KB Output is correct
11 Correct 2570 ms 839064 KB Output is correct
12 Correct 2539 ms 839168 KB Output is correct
13 Correct 2560 ms 838632 KB Output is correct
14 Correct 4006 ms 807280 KB Output is correct
15 Correct 4412 ms 807204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1980 ms 801016 KB Output is correct
18 Correct 2512 ms 807532 KB Output is correct
19 Correct 4118 ms 807296 KB Output is correct
20 Correct 4065 ms 807304 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 4212 ms 807244 KB Output is correct
24 Correct 1895 ms 801088 KB Output is correct
25 Correct 2509 ms 807476 KB Output is correct
26 Correct 3340 ms 547408 KB Output is correct
27 Correct 3398 ms 547468 KB Output is correct
28 Correct 657 ms 50536 KB Output is correct
29 Correct 2516 ms 354096 KB Output is correct
30 Correct 2808 ms 409076 KB Output is correct
31 Correct 1658 ms 503056 KB Output is correct
32 Correct 1780 ms 469444 KB Output is correct
33 Correct 6659 ms 1102016 KB Output is correct
34 Correct 6861 ms 1102428 KB Output is correct
35 Correct 5175 ms 856588 KB Output is correct
36 Correct 3786 ms 1025028 KB Output is correct
37 Correct 3614 ms 1025020 KB Output is correct
38 Correct 3719 ms 1031356 KB Output is correct