Submission #428412

#	Time	Username	Problem	Language	Result	Execution time	Memory
428412		KoD	Road Construction (JOI21_road_construction)	C++17	100 / 100	2761 ms	362580 KiB

road_construction

#include <bits/stdc++.h>

using ll = long long;
template <class T> using Vec = std::vector<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;
Vec<Node> node;

struct Node {
    int left, right;
    std::pair<int, int> value;
    int lch, rch;
};

int makeSol(const int i, const int x = -INF) {
    node.push_back(Node{i, i + 1, std::make_pair(x, i), -1, -1});
    return (int) node.size() - 1;
}

int makePar(const int l, const int r) {
    node.push_back({node[l].left, node[r].right, std::max(node[l].value, node[r].value), l, r});
    return (int) node.size() - 1;
}

int build(const int l, const int r) {
    if (l + 1 == r) return makeSol(l);
    const int m = (l + r) / 2;
    return makePar(build(l, m), build(m, r));
}

int assign(const int n, const int i, const int x) {
    if (node[n].left == i and node[n].right == i + 1) return makeSol(i, x);
    if (i < node[node[n].lch].right) return makePar(assign(node[n].lch, i, x), node[n].rch);
    else return makePar(node[n].lch, assign(node[n].rch, i, x));
}

std::pair<int, int> fold(const int n, const int l, const int r) {
    if (r <= node[n].left or node[n].right <= l) return {-INF, -INF};
    if (l <= node[n].left and node[n].right <= r) return node[n].value;
    return std::max(fold(node[n].lch, l, r), fold(node[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;
        }
    }
    node.reserve(20000000);
    Vec<int> 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:11:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     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