Submission #1112079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112079		Sharky	Road Construction (JOI21_road_construction)	C++17	38 / 100	10040 ms	62280 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, bool add) {
    // cout << "exh: " << di << '\n';
    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());
                // cout << v << " erase " << it->first << '\n';
            }
        }
        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);
                // cout << v << " insert " << it->first << '\n';
            }
        }
        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--;
            // cout << x << ' ' << y << ' ' << it->first << ' ' << sz << '\n';
            // int ex = min(sz, k - cnt);
            // cnt += ex;
            // if (add) {
                for (auto v : ri) {
                    if (lef == y && v == x) continue;
                    if (x == v && y > lef) continue;
                    // cout << '(' << x << ',' << y << ')' << ' ' << '(' << v << ',' << it->first << ')' << '\n';
                    cnt++;
                    if (add) ans.push_back(max(abs(it->first - y), abs(v - x)));
                    if (cnt >= k) return true;
                    // if (ans.size() >= k) return true;
                }
            // }
            if (cnt >= k) {
                // cout << "true!\n";
                return true;
            }
        }
        lb = max(lb, x - di);
        rb = x;
    }
    // cout << "false!\n";
    return false;
}

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) {
        return x[0] - x[1] < y[0] - y[1];
    });
    for (auto& [st, v] : mp) sort(v.begin(), v.end());
    int l = 1, r = 5e9;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid, 0)) r = mid;
        else l = mid + 1;
    }
    // cout << "var: " << l-1 << '\n';
    check(l-1, 1);
    // for (auto x : ans) cout << x << ' ';
    // cout << '\n';
    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 'bool check(long long int, bool)':
road_construction.cpp:20:17: warning: unused variable 'lef' [-Wunused-variable]
   20 |             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: 0 / 27
• Subtask 6: 0 / 35