oj.uz

Submission #1115998

# Submission time Handle Problem Language Result Execution time Memory
1115998 2024-11-21T07:30:08 Z Zero_OP Road Construction (JOI21_road_construction) C++14
100 / 100
 1210 ms 19904 KB 
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    cin >> N >> K;

    vector<pair<long long, long long>> diags;
    for(int i = 0; i < N; ++i){
        long long x, y;
        cin >> x >> y;
        diags.emplace_back(x + y, x - y);
    }

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

    vector<pair<long long, long long>> pts;
    for(int i = 0; i < N; ++i){
        long long x = (diags[i].first + diags[i].second) / 2;
        long long y = diags[i].first - x;
        pts.emplace_back(x, y);
    }

    auto get_dist = [&](int i, int j) -> long long{
        return abs(pts[i].first - pts[j].first) + abs(pts[i].second - pts[j].second);
    };

    auto f = [&](long long d){
        multiset<long long> st;
        int cnt = 0;
        for(int i = 0, j = 0; i < N; ++i){
            while(j < i && diags[i].first - diags[j].first > d){
                st.erase(st.lower_bound(diags[j].second));
                ++j;
            }

            for(auto it = st.lower_bound(diags[i].second - d); it != st.end() && *it <= diags[i].second + d; ++it){
                ++cnt;
                if(cnt >= K) return false;
            }

            st.insert(diags[i].second);
        }
        return true;
    };

    long long l = 1, r = 4e9 + 10, ans = 0;
    while(l <= r){
        long long mid = l + r >> 1;
        if(f(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }

    vector<long long> dists;
    multiset<pair<long long, int>> st;
    const int inf = 1e9;

    for(int i = 0, j = 0; i < N; ++i){
        while(j < i && diags[i].first - diags[j].first > ans){
            st.erase({diags[j].second, j});
            ++j;
        }

        for(auto it = st.lower_bound({diags[i].second - ans, -inf}); it != st.end() && it -> first <= diags[i].second + ans; ++it){
            dists.emplace_back(get_dist(i, it -> second));
        }

        st.insert({diags[i].second, i});
    }

    assert((int)dists.size() < K);
    int n_last = K - (int)dists.size();
    for(int i = 0; i < n_last; ++i) dists.emplace_back(ans + 1);
    sort(dists.begin(), dists.end());

    for(auto it : dists) cout << it << '\n';
    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:53:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         long long mid = l + r >> 1;
      |                         ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5264 KB Output is correct
2 Correct 71 ms 5048 KB Output is correct
3 Correct 64 ms 5256 KB Output is correct
4 Correct 61 ms 5252 KB Output is correct
5 Correct 63 ms 4024 KB Output is correct
6 Correct 3 ms 336 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 16696 KB Output is correct
2 Correct 220 ms 16692 KB Output is correct
3 Correct 83 ms 5048 KB Output is correct
4 Correct 185 ms 16504 KB Output is correct
5 Correct 177 ms 16692 KB Output is correct
6 Correct 171 ms 16948 KB Output is correct
7 Correct 188 ms 16180 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 17724 KB Output is correct
2 Correct 206 ms 17592 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 116 ms 15420 KB Output is correct
5 Correct 206 ms 17856 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 17724 KB Output is correct
2 Correct 206 ms 17592 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 116 ms 15420 KB Output is correct
5 Correct 206 ms 17856 KB Output is correct
6 Correct 294 ms 17592 KB Output is correct
7 Correct 278 ms 17776 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 227 ms 17600 KB Output is correct
11 Correct 97 ms 15640 KB Output is correct
12 Correct 281 ms 17848 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5264 KB Output is correct
2 Correct 71 ms 5048 KB Output is correct
3 Correct 64 ms 5256 KB Output is correct
4 Correct 61 ms 5252 KB Output is correct
5 Correct 63 ms 4024 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 601 ms 10700 KB Output is correct
8 Correct 588 ms 10600 KB Output is correct
9 Correct 64 ms 5304 KB Output is correct
10 Correct 326 ms 10560 KB Output is correct
11 Correct 184 ms 10560 KB Output is correct
12 Correct 197 ms 10756 KB Output is correct
13 Correct 227 ms 10816 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5264 KB Output is correct
2 Correct 71 ms 5048 KB Output is correct
3 Correct 64 ms 5256 KB Output is correct
4 Correct 61 ms 5252 KB Output is correct
5 Correct 63 ms 4024 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 228 ms 16696 KB Output is correct
8 Correct 220 ms 16692 KB Output is correct
9 Correct 83 ms 5048 KB Output is correct
10 Correct 185 ms 16504 KB Output is correct
11 Correct 177 ms 16692 KB Output is correct
12 Correct 171 ms 16948 KB Output is correct
13 Correct 188 ms 16180 KB Output is correct
14 Correct 180 ms 17724 KB Output is correct
15 Correct 206 ms 17592 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 116 ms 15420 KB Output is correct
18 Correct 206 ms 17856 KB Output is correct
19 Correct 294 ms 17592 KB Output is correct
20 Correct 278 ms 17776 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 227 ms 17600 KB Output is correct
24 Correct 97 ms 15640 KB Output is correct
25 Correct 281 ms 17848 KB Output is correct
26 Correct 601 ms 10700 KB Output is correct
27 Correct 588 ms 10600 KB Output is correct
28 Correct 64 ms 5304 KB Output is correct
29 Correct 326 ms 10560 KB Output is correct
30 Correct 184 ms 10560 KB Output is correct
31 Correct 197 ms 10756 KB Output is correct
32 Correct 227 ms 10816 KB Output is correct
33 Correct 1204 ms 19904 KB Output is correct
34 Correct 1210 ms 19756 KB Output is correct
35 Correct 758 ms 18980 KB Output is correct
36 Correct 336 ms 19764 KB Output is correct
37 Correct 293 ms 19764 KB Output is correct
38 Correct 350 ms 18484 KB Output is correct