oj.uz

Submission #770917

# Submission time Handle Problem Language Result Execution time Memory
770917 2023-07-02T06:52:42 Z joshuaZ Road Construction (JOI21_road_construction) C++17
12 / 100
 3867 ms 17640 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int mxN = 250002;

int n, k;
multiset<ll> path;
pll a[mxN];


bool solve(ll d){
    set<pll> st;
    for (int i = 1, j = 1; i <= n; i++){
        while (a[i].first - a[j].first > d){
            st.erase({a[j].second, a[j].first});
            j++;
        }
        auto l = st.lower_bound({a[i].second - d, -1e10});
        auto r = st.upper_bound({a[i].second + d, -1e10});
        for (auto it = l; it != r; it++){
            path.insert(max(abs((*it).second - a[i].first), abs((*it).first - a[i].second)));
            if (path.size() >= k){
                return true;
            }
        }
        st.insert({a[i].second, a[i].first});
    }

    if (path.size() >= k){
        return true;
    } else {
        return false;
    }
}

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

    cin >> n >> k;
    //xi + yi - (xj + yj) <= val
    //xi - xj + yi - yj
    //xi - yi - (xj - yj) <= val
    //xi - xj + yj - yi <= val
    for (int i = 1; i <= n; i++){
        ll x, y; cin >> x >> y;
        a[i].first = x + y;
        a[i].second = x - y;
    }
    sort(a + 1, a + 1 + n);

    ll lo = 1, hi = 5e9, ans = -1;
    while (lo <= hi){
        ll mid = lo + (hi - lo) / 2;
        if (solve(mid)){
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
        path.clear();
    }

    solve(ans);

    int c = 1;
    for (auto &x : path){
        cout << x << '\n';
        if (c++ >= k){
            break;
        }
    }
}

Compilation message

road_construction.cpp: In function 'bool solve(ll)':
road_construction.cpp:23:29: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |             if (path.size() >= k){
      |                 ~~~~~~~~~~~~^~~~
road_construction.cpp:30:21: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |     if (path.size() >= k){
      |         ~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3853 ms 14696 KB Output is correct
2 Correct 3580 ms 14700 KB Output is correct
3 Correct 3288 ms 14664 KB Output is correct
4 Correct 3211 ms 14704 KB Output is correct
5 Correct 3194 ms 13608 KB Output is correct
6 Correct 6 ms 468 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3250 ms 17404 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 173 ms 4576 KB Output is correct
2 Correct 247 ms 4480 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 98 ms 7080 KB Output is correct
5 Correct 344 ms 9616 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 4576 KB Output is correct
2 Correct 247 ms 4480 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 98 ms 7080 KB Output is correct
5 Correct 344 ms 9616 KB Output is correct
6 Correct 389 ms 9304 KB Output is correct
7 Correct 335 ms 9404 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 279 ms 9308 KB Output is correct
11 Correct 96 ms 7152 KB Output is correct
12 Incorrect 367 ms 9592 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3853 ms 14696 KB Output is correct
2 Correct 3580 ms 14700 KB Output is correct
3 Correct 3288 ms 14664 KB Output is correct
4 Correct 3211 ms 14704 KB Output is correct
5 Correct 3194 ms 13608 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 3617 ms 17640 KB Output is correct
8 Correct 3867 ms 17628 KB Output is correct
9 Correct 2769 ms 14804 KB Output is correct
10 Incorrect 3419 ms 16980 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3853 ms 14696 KB Output is correct
2 Correct 3580 ms 14700 KB Output is correct
3 Correct 3288 ms 14664 KB Output is correct
4 Correct 3211 ms 14704 KB Output is correct
5 Correct 3194 ms 13608 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Incorrect 3250 ms 17404 KB Output isn't correct
8 Halted 0 ms 0 KB -