Submission #935556

#	Time	Username	Problem	Language	Result	Execution time	Memory
935556		Pannda	Road Construction (JOI21_road_construction)	C++17	100 / 100	6111 ms	47272 KiB

road_construction

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

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