oj.uz

Submission #770920

# Submission time Handle Problem Language Result Execution time Memory
770920 2023-07-02T06:55:15 Z joshuaZ Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 41180 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() >= 3 * mxN){
                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: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 4886 ms 25228 KB Output is correct
2 Correct 4838 ms 25084 KB Output is correct
3 Correct 3295 ms 14664 KB Output is correct
4 Correct 3372 ms 14796 KB Output is correct
5 Correct 4323 ms 24580 KB Output is correct
6 Correct 352 ms 23884 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10079 ms 40032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7013 ms 39904 KB Output is correct
2 Correct 6856 ms 40288 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 9972 ms 41052 KB Output is correct
5 Correct 5669 ms 41180 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7013 ms 39904 KB Output is correct
2 Correct 6856 ms 40288 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 9972 ms 41052 KB Output is correct
5 Correct 5669 ms 41180 KB Output is correct
6 Correct 6997 ms 41060 KB Output is correct
7 Correct 6824 ms 41052 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 7005 ms 41108 KB Output is correct
11 Correct 9694 ms 41040 KB Output is correct
12 Correct 5871 ms 41072 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4886 ms 25228 KB Output is correct
2 Correct 4838 ms 25084 KB Output is correct
3 Correct 3295 ms 14664 KB Output is correct
4 Correct 3372 ms 14796 KB Output is correct
5 Correct 4323 ms 24580 KB Output is correct
6 Correct 352 ms 23884 KB Output is correct
7 Execution timed out 10079 ms 37176 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4886 ms 25228 KB Output is correct
2 Correct 4838 ms 25084 KB Output is correct
3 Correct 3295 ms 14664 KB Output is correct
4 Correct 3372 ms 14796 KB Output is correct
5 Correct 4323 ms 24580 KB Output is correct
6 Correct 352 ms 23884 KB Output is correct
7 Execution timed out 10079 ms 40032 KB Time limit exceeded
8 Halted 0 ms 0 KB -