oj.uz

Submission #575470

# Submission time Handle Problem Language Result Execution time Memory
575470 2022-06-10T18:00:55 Z rainliofficial Road Construction (JOI21_road_construction) C++17
12 / 100
 981 ms 10548 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define sz(x) (int)x.size()
#define f first
#define s second

/* 
Date: 2022/06/10
Problem Link: https://oj.uz/problem/view/JOI21_road_construction
Topic(s): Binary search, sorting
Time Spent: 
Solution Outline:
- The distance between two points can be written as max(abs((xi + yi) - (xj + yj)), abs((xi - yi) - (xj - yj)))
Binary search on v, which is the kth largest value. We have to check whether there more or less than k roads with
cost <= v. 
- Maintain a sliding window of size v. 
- Sort the points by xi + yi. For a point i, remove all points j that has xj + yj further than v units away.
- Put xi - yi into the set. 
- We know all js that came before i must have xi + yi - (xj + yj) <= v. So we can simply call lower_bound on the set
with xi - yi - v and vi - vi + v. The range that it gives us will be the amount of points within v distance of i. 
*/

const int MAXN = 2e5+5;
int n, k;
vector<pll> arr;
vector<ll> res;

ll sum(const pll& a){
    return a.f + a.s;
}
ll dif(const pll& a){
    return a.f - a.s;
}


bool check(ll v, bool upd){
    int l = 0;
    auto cmp = [](const pll& a, const pll& b){
        if (dif(a) == dif(b)){
            return a < b;
        }else{
            return a.f - a.s < b.f - b.s;
        }
    };
    set<pll, decltype(cmp)> set(cmp);
    set.insert({0, 1});
    set.insert({0, 1});
    set.erase({0, 1});
    ll ans = 0;
    for (int i=0; i<n; i++){
        while (l < n && sum(arr[i]) - sum(arr[l]) > v){
            set.erase(arr[l]);
            l++;
        }
        auto inc = set.lower_bound(arr[i]);
        auto dec = inc;
        while (inc != set.end() && dif(*inc) - dif(arr[i]) <= v && ans <= k){
            if (upd) res.push_back(abs(arr[i].f - (*inc).f) + abs(arr[i].s - (*inc).s));
            inc++;
            ans++;
        }
        while (dec != set.begin() && dif(arr[i]) - dif(*prev(dec)) <= v && ans <= k){
            dec--;
            if (upd) res.push_back(abs(arr[i].f - (*dec).f) + abs(arr[i].s - (*dec).s));
            ans++;
        }
        if (ans >= k){
            return true;
        }
        set.insert(arr[i]);
    }
    return ans >= k;
}
int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    cin >> n >> k;
    arr.resize(n);
    for (int i=0; i<n; i++){
        int x, y;
        cin >> x >> y;
        arr[i] = {x, y};
    }
    sort(arr.begin(), arr.end(), [](const pll& a, const pll& b){
        return a.f + a.s < b.f + b.s;
    });
    ll low = 0, high = 4e9;
    while (low < high){
        ll mid = (low + high)/2;
        if (check(mid, false)){
            high = mid;
        }else{
            low = mid+1;
        }
    }
    check(low, true);
    assert(res.size() >= k);
    sort(res.begin(), res.end());
    for (int i=0; i<k; i++){
        cout << res[i] << "\n";
    }
}

Compilation message

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: In function 'int main()':
road_construction.cpp:100:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |     assert(res.size() >= k);
      |            ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4984 KB Output is correct
2 Correct 130 ms 4976 KB Output is correct
3 Correct 117 ms 5088 KB Output is correct
4 Correct 107 ms 5092 KB Output is correct
5 Correct 123 ms 3832 KB Output is correct
6 Correct 6 ms 340 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 378 ms 10548 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 227 ms 9212 KB Output is correct
2 Correct 317 ms 9204 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 139 ms 7024 KB Output is correct
5 Correct 634 ms 9520 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 9212 KB Output is correct
2 Correct 317 ms 9204 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 139 ms 7024 KB Output is correct
5 Correct 634 ms 9520 KB Output is correct
6 Correct 484 ms 9208 KB Output is correct
7 Correct 428 ms 9216 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 328 ms 9216 KB Output is correct
11 Correct 102 ms 7040 KB Output is correct
12 Incorrect 700 ms 9596 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4984 KB Output is correct
2 Correct 130 ms 4976 KB Output is correct
3 Correct 117 ms 5088 KB Output is correct
4 Correct 107 ms 5092 KB Output is correct
5 Correct 123 ms 3832 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 981 ms 8064 KB Output is correct
8 Correct 976 ms 8064 KB Output is correct
9 Correct 109 ms 5212 KB Output is correct
10 Incorrect 518 ms 7276 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4984 KB Output is correct
2 Correct 130 ms 4976 KB Output is correct
3 Correct 117 ms 5088 KB Output is correct
4 Correct 107 ms 5092 KB Output is correct
5 Correct 123 ms 3832 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Incorrect 378 ms 10548 KB Output isn't correct
8 Halted 0 ms 0 KB -