oj.uz

Submission #995525

# Submission time Handle Problem Language Result Execution time Memory
995525 2024-06-09T09:08:42 Z vladilius Road Construction (JOI21_road_construction) C++17
0 / 100
 214 ms 7504 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const int inf = 1e9;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k; cin>>n>>k;
    vector<pii> p(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>p[i].ff>>p[i].ss;
    }
    sort(p.begin() + 1, p.end());
    vector<ll> dist;
    auto get = [&](ll r){
        multiset<pii> st;
        int j = 1;
        for (int i = 1; i <= n; i++){
            if (dist.size() >= k) break;
            while (j < i && (p[i].ff - p[j].ff) > r){
                st.erase(st.find(p[j]));
                j++;
            }
            auto it = st.lower_bound({-inf, p[i].ss - r});
            ll R = p[i].ss + r;
            while (it != st.end() && (*it).ss <= R && dist.size() < k){
                ll d = abs(p[i].ff - (*it).ff) + abs(p[i].ss - (*it).ss);
                if (d <= r){
                    dist.pb(d);
                }
                it++;
            }
            st.insert(p[i]);
        }
    };
    
    ll l = 0, r = 4LL * inf;
    while (l + 1 < r){
        ll m = (l + r) / 2;
        get(m);
        if (dist.size() < k){
            l = m + 1;
        }
        else {
            r = m;
        }
        dist.clear();
    }
    get(r);
    sort(dist.begin(), dist.end());
    for (int i = 0; i < k; i++){
        cout<<dist[i]<<"\n";
    }
}

Compilation message

road_construction.cpp: In lambda function:
road_construction.cpp:27:29: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |             if (dist.size() >= k) break;
      |                 ~~~~~~~~~~~~^~~~
road_construction.cpp:34:67: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |             while (it != st.end() && (*it).ss <= R && dist.size() < k){
      |                                                       ~~~~~~~~~~~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:49:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         if (dist.size() < k){
      |             ~~~~~~~~~~~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 5128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 5616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 2396 KB Output is correct
2 Correct 194 ms 7504 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 2396 KB Output is correct
2 Correct 194 ms 7504 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 5128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 5128 KB Output isn't correct
2 Halted 0 ms 0 KB -