Submission #1112343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112343		Sharky	Road Construction (JOI21_road_construction)	C++17	100 / 100	6289 ms	68280 KiB

road_construction

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

#define int long long
const int N = 2.5e5 + 10;
int n, k;
array<int, 2> a[N];
map<int, vector<int>> mp;
vector<int> ans;

bool check(int di) {
    map<int, int> f;
    int cnt = 0, ptr = 1;
    for (int i = 1; i <= n; i++) {
        int x = a[i][0] - a[i][1], y = a[i][0] + a[i][1];
        while (ptr < i && a[ptr][0] - a[ptr][1] < x - di) {
            if (!--f[a[ptr][0] + a[ptr][1]]) f.erase(a[ptr][0] + a[ptr][1]);
            ptr++;
        }
        for (auto it = f.lower_bound(y - di); it != f.end() && it->first <= y + di; it++) {
            cnt += f[it->first];
            if (cnt >= k) return true;
        }
        f[y]++;
    }
    return false;
}

void out(int di) {
    map<int, vector<int>> f;
    int cnt = 0;
    int lb = -1e18, rb = -1e18;
    for (int i = 1; i <= n; i++) {
        int x = a[i][0] - a[i][1], y = a[i][0] + a[i][1];
        for (auto it = mp.lower_bound(lb); it != mp.end() && it->first < x - di; it++) {
            auto& ri = it->second;
            int lef = it->first;
            for (auto& v : ri) {
                f[v].erase(f[v].begin());
            }
        }
        for (auto it = mp.lower_bound(max(x - di, rb + 1)); it != mp.end() && it->first <= x; it++) {
            auto& ri = it->second;
            int lef = it->first;
            for (auto& v : ri) {
                f[v].push_back(lef);
            }
        }
        for (auto it = f.lower_bound(y-di); it != f.end() && it->first <= y + di; it++) {
            int lef = it->first;
            auto& ri = it->second;
            int sz = ri.size();
            if (lef == y) sz--;
            for (auto v : ri) {
                if (lef == y && v == x) continue;
                if (x == v && y > lef) continue;
                // cout << '(' << x << ',' << y << ')' << ' ' << '(' << v << ',' << it->first << ')' << '\n';
                cnt++;
                ans.push_back(max(abs(it->first - y), abs(v - x)));
                if (cnt >= k) return;
            }
        }
        lb = max(lb, x - di);
        rb = x;
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1];
        mp[a[i][0] - a[i][1]].push_back(a[i][0] + a[i][1]);
    }
    sort(a + 1, a + n + 1, [] (array<int, 2> x, array<int, 2> y) {
        if (x[0] - x[1] == y[0] - y[1]) return x[0] + x[1] < y[0] + y[1];
        return x[0] - x[1] < y[0] - y[1];
    });
    int l = 1, r = 4e9;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    out(l - 1);
    sort(ans.begin(), ans.end());
    while (ans.size() < k) ans.push_back(l);
    for (int i = 0; i < k; i++) cout << ans[i] << '\n';
    return 0;
}
/*
5 4
-2 2
-1 -1
2 0
2 2
2 -2
*/

Compilation message (stderr)

road_construction.cpp: In function 'void out(long long int)':
road_construction.cpp:37:17: warning: unused variable 'lef' [-Wunused-variable]
   37 |             int lef = it->first;
      |                 ^~~
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:87:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   87 |     while (ans.size() < k) ans.push_back(l);
      |            ~~~~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35