oj.uz

Submission #995528

# Submission time Handle Problem Language Result Execution time Memory
995528 2024-06-09T09:26:58 Z vladilius Road Construction (JOI21_road_construction) C++17
7 / 100
 308 ms 9696 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const ll 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].ss, p[j].ff}));
                j++;
            }
            auto it = st.lower_bound({p[i].ss - r, -inf});
            ll R = p[i].ss + r;
            while (it != st.end() && (*it).ff <= R && dist.size() < k){
                ll d = abs(p[i].ff - (*it).ss) + abs(p[i].ss - (*it).ff);
                if (d <= r){
                    dist.pb(d);
                }
                it++;
            }
            st.insert({p[i].ss, p[i].ff});
        }
    };
    
    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);
    assert(dist.size() >= k);
    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).ff <= 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){
      |             ~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from road_construction.cpp:1:
road_construction.cpp:58:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     assert(dist.size() >= k);
      |            ~~~~~~~~~~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 5072 KB Output is correct
2 Correct 120 ms 5160 KB Output is correct
3 Correct 76 ms 5068 KB Output is correct
4 Correct 83 ms 5128 KB Output is correct
5 Incorrect 76 ms 4048 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 6996 KB Output is correct
2 Correct 208 ms 7064 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 84 ms 7260 KB Output is correct
5 Correct 190 ms 9696 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 6996 KB Output is correct
2 Correct 208 ms 7064 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 84 ms 7260 KB Output is correct
5 Correct 190 ms 9696 KB Output is correct
6 Correct 308 ms 9352 KB Output is correct
7 Correct 266 ms 9296 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 216 ms 9448 KB Output is correct
11 Correct 70 ms 7252 KB Output is correct
12 Incorrect 191 ms 9608 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 5072 KB Output is correct
2 Correct 120 ms 5160 KB Output is correct
3 Correct 76 ms 5068 KB Output is correct
4 Correct 83 ms 5128 KB Output is correct
5 Incorrect 76 ms 4048 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 5072 KB Output is correct
2 Correct 120 ms 5160 KB Output is correct
3 Correct 76 ms 5068 KB Output is correct
4 Correct 83 ms 5128 KB Output is correct
5 Incorrect 76 ms 4048 KB Output isn't correct
6 Halted 0 ms 0 KB -