oj.uz

Submission #705792

# Submission time Handle Problem Language Result Execution time Memory
705792 2023-03-05T09:37:26 Z bebra Road Construction (JOI21_road_construction) C++17
100 / 100
 2320 ms 15972 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long

#define dbg(x) cerr << #x << ": " << x << endl;


struct FenwickTree {
    vector<int> tree;
    int size;

    FenwickTree(int n) {
        size = n;
        tree.resize(n);
    }

    void update(int pos, int value) {
        for (int i = pos; i < size; i |= i + 1) {
            tree[i] += value;
        }
    }

    int query(int l, int r) {
        int res = 0;
        for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
            res += tree[i];
        }
        for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) {
            res -= tree[i];
        }
        return res;
    }
};


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> points(n);
    vector<int> coords;
    for (auto& [x, y] : points) {
        cin >> x >> y;
        int x0 = x;
        int y0 = y;
        x = x0 + y0;
        y = x0 - y0;
        coords.push_back(y);
    }

    sort(points.begin(), points.end());

    sort(coords.begin(), coords.end());
    coords.resize(unique(coords.begin(), coords.end()) - coords.begin());
    for (auto& [x, y] : points) {
        y = lower_bound(coords.begin(), coords.end(), y) - coords.begin();
    }

    auto check = [&](ll dist) {
        FenwickTree tree(coords.size());
        int res = 0;
        int p = 0;
        for (int i = 0; i < n; ++i) {
            while (points[i].first - points[p].first > dist) {
                tree.update(points[p].second, -1);
                ++p;
            }
            int l = lower_bound(coords.begin(), coords.end(), coords[points[i].second] - dist) - coords.begin();
            int r = upper_bound(coords.begin(), coords.end(), coords[points[i].second] + dist) - coords.begin() - 1;
            res += tree.query(l, r);
            tree.update(points[i].second, 1);
            if (res >= k) return true;
        }
        return res >= k;
    };

    ll dist;
    {
        ll l = -1;
        ll r = 4e9 + 1;
        while (l != r - 1) {
            ll m = (l + r) / 2;
            if (check(m)) {
                r = m;
            } else {
                l = m;
            }
        }
        dist = l;
    }

    vector<ll> ans;
    ans.reserve(k);

    set<pair<ll, int>> s;
    int p = 0;
    for (int i = 0; i < n; ++i) {
        while (points[i].first - points[p].first > dist) {
            s.erase({coords[points[p].second], p});
            ++p;
        }
        auto it = s.lower_bound({coords[points[i].second] - dist, -1});
        while (it != s.end() && it->first <= coords[points[i].second] + dist) {
            int j = it->second;
            ll curr_dist = max(abs(points[i].first - points[j].first), abs(coords[points[i].second] - coords[points[j].second]));
            ans.push_back(curr_dist);
            ++it;
        }
        s.emplace(coords[points[i].second], i);
    }

    while ((int)ans.size() < k) {
        ans.push_back(dist + 1);
    }
    sort(ans.begin(), ans.end());

    for (auto x : ans) {
        cout << x << '\n';
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4816 KB Output is correct
2 Correct 49 ms 4924 KB Output is correct
3 Correct 36 ms 4908 KB Output is correct
4 Correct 37 ms 5044 KB Output is correct
5 Correct 37 ms 3780 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 9372 KB Output is correct
2 Correct 674 ms 9432 KB Output is correct
3 Correct 40 ms 4820 KB Output is correct
4 Correct 628 ms 9116 KB Output is correct
5 Correct 549 ms 9300 KB Output is correct
6 Correct 506 ms 9384 KB Output is correct
7 Correct 477 ms 8536 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1059 ms 8260 KB Output is correct
2 Correct 1205 ms 8244 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 357 ms 8244 KB Output is correct
5 Correct 297 ms 6476 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1059 ms 8260 KB Output is correct
2 Correct 1205 ms 8244 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 357 ms 8244 KB Output is correct
5 Correct 297 ms 6476 KB Output is correct
6 Correct 1397 ms 8248 KB Output is correct
7 Correct 1342 ms 8260 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1381 ms 13240 KB Output is correct
11 Correct 321 ms 11188 KB Output is correct
12 Correct 325 ms 11556 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4816 KB Output is correct
2 Correct 49 ms 4924 KB Output is correct
3 Correct 36 ms 4908 KB Output is correct
4 Correct 37 ms 5044 KB Output is correct
5 Correct 37 ms 3780 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 876 ms 9372 KB Output is correct
8 Correct 904 ms 9548 KB Output is correct
9 Correct 38 ms 5044 KB Output is correct
10 Correct 657 ms 8588 KB Output is correct
11 Correct 516 ms 8380 KB Output is correct
12 Correct 190 ms 8904 KB Output is correct
13 Correct 205 ms 7372 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4816 KB Output is correct
2 Correct 49 ms 4924 KB Output is correct
3 Correct 36 ms 4908 KB Output is correct
4 Correct 37 ms 5044 KB Output is correct
5 Correct 37 ms 3780 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 681 ms 9372 KB Output is correct
8 Correct 674 ms 9432 KB Output is correct
9 Correct 40 ms 4820 KB Output is correct
10 Correct 628 ms 9116 KB Output is correct
11 Correct 549 ms 9300 KB Output is correct
12 Correct 506 ms 9384 KB Output is correct
13 Correct 477 ms 8536 KB Output is correct
14 Correct 1059 ms 8260 KB Output is correct
15 Correct 1205 ms 8244 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 357 ms 8244 KB Output is correct
18 Correct 297 ms 6476 KB Output is correct
19 Correct 1397 ms 8248 KB Output is correct
20 Correct 1342 ms 8260 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1381 ms 13240 KB Output is correct
24 Correct 321 ms 11188 KB Output is correct
25 Correct 325 ms 11556 KB Output is correct
26 Correct 876 ms 9372 KB Output is correct
27 Correct 904 ms 9548 KB Output is correct
28 Correct 38 ms 5044 KB Output is correct
29 Correct 657 ms 8588 KB Output is correct
30 Correct 516 ms 8380 KB Output is correct
31 Correct 190 ms 8904 KB Output is correct
32 Correct 205 ms 7372 KB Output is correct
33 Correct 2320 ms 15164 KB Output is correct
34 Correct 2267 ms 15160 KB Output is correct
35 Correct 2009 ms 15972 KB Output is correct
36 Correct 373 ms 15300 KB Output is correct
37 Correct 355 ms 15264 KB Output is correct
38 Correct 497 ms 14176 KB Output is correct