Submission #428388

#	Time	Username	Problem	Language	Result	Execution time	Memory
428388		KoD	Road Construction (JOI21_road_construction)	C++17	100 / 100	6861 ms	1102428 KiB

road_construction

#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 (stderr)

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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35