oj.uz

Submission #935556

# Submission time Handle Problem Language Result Execution time Memory
935556 2024-02-29T09:08:23 Z Pannda Road Construction (JOI21_road_construction) C++17
100 / 100
 6111 ms 47272 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set __gnu_pbds::tree<array<long long, 2>, __gnu_pbds::null_type, less<array<long long, 2>>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>
const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<array<int, 2>> a(n);
    for (int i = 0; i < n; i++) {
        int x0, y0;
        cin >> x0 >> y0;
        int x = x0 - y0;
        int y = x0 + y0;
        a[i] = {x, y};
    }

    auto countPair = [](vector<array<int, 2>> a, long long dist) -> long long { // returns number of pairs with distance <= 'dist'
        vector<array<long long, 4>> events; // {x, erase:1 insert:0, y}
        for (auto [x, y] : a) {
            events.push_back({x, 0, x, y});
            events.push_back({x + dist, 1, x, y});
        }
        sort(events.begin(), events.end());
        ordered_set st;
        long long res = 0;
        for (auto [t, type, x, y] : events) {
            if (type == 0) {
                res += st.order_of_key(array<long long, 2>{y + dist, +INF}) - st.order_of_key(array<long long, 2>{y - dist, -INF});
                st.insert(array<long long, 2>{y, x});
            }
            if (type == 1) {
                st.erase(st.lower_bound({y, x}));
            }
        }
        return res;
    };

    long long dist = [&]() -> long long {
        long long l = 0, r = (long long)4e9 + 12345;
        while (l < r) {
            long long m = (l + r) >> 1;
            if (countPair(a, m) >= k) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }();

    for (long long x : [&]() -> vector<long long> {
            vector<array<long long, 4>> events; // {x, erase:1 insert:0, y}
            for (auto [x, y] : a) {
                events.push_back({x, 0, x, y});
                events.push_back({x + (dist - 1), 1, x, y});
            }
            sort(events.begin(), events.end());
            ordered_set st;
            vector<long long> res;
            for (auto [t, type, x, y] : events) {
                if (type == 0) {
                    auto it = st.lower_bound(array<long long, 2>{y - (dist - 1), -INF});
                    while (it != st.end() && (*it)[0] <= y + (dist - 1)) {
                        long long d = max(abs(y - (*it)[0]), abs(x - (*it)[1]));
                        res.push_back(d);
                        it++;
                    }
                    st.insert({y, x});
                }
                if (type == 1) {
                    st.erase(st.lower_bound(array<long long, 2>{y, x}));
                }
            }
            assert(res.size() < k);
            while (res.size() < k) res.push_back(dist);
            sort(res.begin(), res.end());
            return res;
        }()) {
        cout << x << '\n';
    }
}

Compilation message

In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from road_construction.cpp:4:
road_construction.cpp: In lambda function:
road_construction.cpp:82:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |             assert(res.size() < k);
      |                    ~~~~~~~~~~~^~~
road_construction.cpp:83:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |             while (res.size() < k) res.push_back(dist);
      |                    ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5060 KB Output is correct
2 Correct 49 ms 5120 KB Output is correct
3 Correct 42 ms 5376 KB Output is correct
4 Correct 41 ms 5372 KB Output is correct
5 Correct 44 ms 4024 KB Output is correct
6 Correct 12 ms 600 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3556 ms 43256 KB Output is correct
2 Correct 3509 ms 43188 KB Output is correct
3 Correct 36 ms 5220 KB Output is correct
4 Correct 3582 ms 43200 KB Output is correct
5 Correct 4568 ms 41152 KB Output is correct
6 Correct 4492 ms 42628 KB Output is correct
7 Correct 3786 ms 47272 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4182 ms 45560 KB Output is correct
2 Correct 4192 ms 43392 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4363 ms 42592 KB Output is correct
5 Correct 5229 ms 46084 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4182 ms 45560 KB Output is correct
2 Correct 4192 ms 43392 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4363 ms 42592 KB Output is correct
5 Correct 5229 ms 46084 KB Output is correct
6 Correct 4125 ms 44076 KB Output is correct
7 Correct 4339 ms 44084 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 4062 ms 46104 KB Output is correct
11 Correct 4350 ms 42508 KB Output is correct
12 Correct 5152 ms 45868 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5060 KB Output is correct
2 Correct 49 ms 5120 KB Output is correct
3 Correct 42 ms 5376 KB Output is correct
4 Correct 41 ms 5372 KB Output is correct
5 Correct 44 ms 4024 KB Output is correct
6 Correct 12 ms 600 KB Output is correct
7 Correct 2122 ms 20924 KB Output is correct
8 Correct 2161 ms 21712 KB Output is correct
9 Correct 42 ms 5256 KB Output is correct
10 Correct 1788 ms 21852 KB Output is correct
11 Correct 1501 ms 21088 KB Output is correct
12 Correct 1836 ms 20560 KB Output is correct
13 Correct 2229 ms 20880 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5060 KB Output is correct
2 Correct 49 ms 5120 KB Output is correct
3 Correct 42 ms 5376 KB Output is correct
4 Correct 41 ms 5372 KB Output is correct
5 Correct 44 ms 4024 KB Output is correct
6 Correct 12 ms 600 KB Output is correct
7 Correct 3556 ms 43256 KB Output is correct
8 Correct 3509 ms 43188 KB Output is correct
9 Correct 36 ms 5220 KB Output is correct
10 Correct 3582 ms 43200 KB Output is correct
11 Correct 4568 ms 41152 KB Output is correct
12 Correct 4492 ms 42628 KB Output is correct
13 Correct 3786 ms 47272 KB Output is correct
14 Correct 4182 ms 45560 KB Output is correct
15 Correct 4192 ms 43392 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 4363 ms 42592 KB Output is correct
18 Correct 5229 ms 46084 KB Output is correct
19 Correct 4125 ms 44076 KB Output is correct
20 Correct 4339 ms 44084 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 4062 ms 46104 KB Output is correct
24 Correct 4350 ms 42508 KB Output is correct
25 Correct 5152 ms 45868 KB Output is correct
26 Correct 2122 ms 20924 KB Output is correct
27 Correct 2161 ms 21712 KB Output is correct
28 Correct 42 ms 5256 KB Output is correct
29 Correct 1788 ms 21852 KB Output is correct
30 Correct 1501 ms 21088 KB Output is correct
31 Correct 1836 ms 20560 KB Output is correct
32 Correct 2229 ms 20880 KB Output is correct
33 Correct 6111 ms 44552 KB Output is correct
34 Correct 5739 ms 43304 KB Output is correct
35 Correct 4789 ms 43340 KB Output is correct
36 Correct 5364 ms 44536 KB Output is correct
37 Correct 5277 ms 43184 KB Output is correct
38 Correct 5449 ms 45444 KB Output is correct