oj.uz

Submission #428412

# Submission time Handle Problem Language Result Execution time Memory
428412 2021-06-15T11:33:04 Z KoD Road Construction (JOI21_road_construction) C++17
100 / 100
 2761 ms 362580 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 67908 KB Output is correct
2 Correct 380 ms 67908 KB Output is correct
3 Correct 319 ms 65240 KB Output is correct
4 Correct 278 ms 65172 KB Output is correct
5 Correct 349 ms 66812 KB Output is correct
6 Correct 4 ms 1484 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1318 ms 359200 KB Output is correct
2 Correct 1301 ms 359372 KB Output is correct
3 Correct 239 ms 64964 KB Output is correct
4 Correct 878 ms 358980 KB Output is correct
5 Correct 889 ms 359208 KB Output is correct
6 Correct 836 ms 359192 KB Output is correct
7 Correct 907 ms 358736 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1401 ms 251080 KB Output is correct
2 Correct 1412 ms 251156 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 528 ms 246912 KB Output is correct
5 Correct 744 ms 250992 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1401 ms 251080 KB Output is correct
2 Correct 1412 ms 251156 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 528 ms 246912 KB Output is correct
5 Correct 744 ms 250992 KB Output is correct
6 Correct 1483 ms 251056 KB Output is correct
7 Correct 1450 ms 251108 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 1458 ms 251040 KB Output is correct
11 Correct 513 ms 246916 KB Output is correct
12 Correct 835 ms 251044 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 67908 KB Output is correct
2 Correct 380 ms 67908 KB Output is correct
3 Correct 319 ms 65240 KB Output is correct
4 Correct 278 ms 65172 KB Output is correct
5 Correct 349 ms 66812 KB Output is correct
6 Correct 4 ms 1484 KB Output is correct
7 Correct 1753 ms 201348 KB Output is correct
8 Correct 1696 ms 201340 KB Output is correct
9 Correct 326 ms 65180 KB Output is correct
10 Correct 1078 ms 200556 KB Output is correct
11 Correct 1282 ms 200476 KB Output is correct
12 Correct 647 ms 201300 KB Output is correct
13 Correct 732 ms 199936 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 67908 KB Output is correct
2 Correct 380 ms 67908 KB Output is correct
3 Correct 319 ms 65240 KB Output is correct
4 Correct 278 ms 65172 KB Output is correct
5 Correct 349 ms 66812 KB Output is correct
6 Correct 4 ms 1484 KB Output is correct
7 Correct 1318 ms 359200 KB Output is correct
8 Correct 1301 ms 359372 KB Output is correct
9 Correct 239 ms 64964 KB Output is correct
10 Correct 878 ms 358980 KB Output is correct
11 Correct 889 ms 359208 KB Output is correct
12 Correct 836 ms 359192 KB Output is correct
13 Correct 907 ms 358736 KB Output is correct
14 Correct 1401 ms 251080 KB Output is correct
15 Correct 1412 ms 251156 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 528 ms 246912 KB Output is correct
18 Correct 744 ms 250992 KB Output is correct
19 Correct 1483 ms 251056 KB Output is correct
20 Correct 1450 ms 251108 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 288 KB Output is correct
23 Correct 1458 ms 251040 KB Output is correct
24 Correct 513 ms 246916 KB Output is correct
25 Correct 835 ms 251044 KB Output is correct
26 Correct 1753 ms 201348 KB Output is correct
27 Correct 1696 ms 201340 KB Output is correct
28 Correct 326 ms 65180 KB Output is correct
29 Correct 1078 ms 200556 KB Output is correct
30 Correct 1282 ms 200476 KB Output is correct
31 Correct 647 ms 201300 KB Output is correct
32 Correct 732 ms 199936 KB Output is correct
33 Correct 2761 ms 362580 KB Output is correct
34 Correct 2729 ms 362516 KB Output is correct
35 Correct 1943 ms 361764 KB Output is correct
36 Correct 1276 ms 362264 KB Output is correct
37 Correct 1266 ms 362560 KB Output is correct
38 Correct 1334 ms 361012 KB Output is correct