oj.uz

Submission #705791

# Submission time Handle Problem Language Result Execution time Memory
705791 2023-03-05T09:35:44 Z bebra Road Construction (JOI21_road_construction) C++17
13 / 100
 1362 ms 10472 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = 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;
    }
};


int 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4908 KB Output is correct
2 Correct 45 ms 4948 KB Output is correct
3 Incorrect 39 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 10352 KB Output is correct
2 Correct 700 ms 10348 KB Output is correct
3 Correct 36 ms 4812 KB Output is correct
4 Correct 632 ms 10228 KB Output is correct
5 Correct 588 ms 10376 KB Output is correct
6 Correct 528 ms 10472 KB Output is correct
7 Correct 491 ms 9920 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 9376 KB Output is correct
2 Correct 1211 ms 9348 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 363 ms 7264 KB Output is correct
5 Correct 304 ms 8648 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 9376 KB Output is correct
2 Correct 1211 ms 9348 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 363 ms 7264 KB Output is correct
5 Correct 304 ms 8648 KB Output is correct
6 Correct 1362 ms 9392 KB Output is correct
7 Correct 1280 ms 9424 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4908 KB Output is correct
2 Correct 45 ms 4948 KB Output is correct
3 Incorrect 39 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4908 KB Output is correct
2 Correct 45 ms 4948 KB Output is correct
3 Incorrect 39 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -