Submission #935569

#	Time	Username	Problem	Language	Result	Execution time	Memory
935569		Pannda	Road Construction (JOI21_road_construction)	C++17	100 / 100	6643 ms	41348 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

struct Fenwick {
    int n;
    vector<int> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int i, int delta) {
        for (i++; i <= n; i += i & -i) {
            bit[i] += delta;
        }
    }

    int sum(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) {
            res += bit[i];
        }
        return res;
    }
};

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

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

    vector<array<int, 2>> a(n);
    vector<long long> ys;
    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};
        ys.push_back(y);
    }
    sort(ys.begin(), ys.end());
    ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
    int C = ys.size();

    auto countPair = [&ys, &C, &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());
        Fenwick fen(C);
        long long res = 0;
        for (auto [t, type, x, y] : events) {
            if (type == 0) {
                res += fen.sum(upper_bound(ys.begin(), ys.end(), y + dist) - ys.begin()) - fen.sum(lower_bound(ys.begin(), ys.end(), y - dist) - ys.begin());
                fen.add(lower_bound(ys.begin(), ys.end(), y) - ys.begin(), +1);
            }
            if (type == 1) {
                fen.add(lower_bound(ys.begin(), ys.end(), y) - ys.begin(), -1);
            }
        }
        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(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());
            set<array<long long, 2>> 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/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from road_construction.cpp:1:
road_construction.cpp: In lambda function:
road_construction.cpp:105:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |             assert(res.size() < k);
      |                    ~~~~~~~~~~~^~~
road_construction.cpp:106:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |             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