oj.uz

Submission #601166

# Submission time Handle Problem Language Result Execution time Memory
601166 2022-07-21T12:16:37 Z lordlorinc Road Construction (JOI21_road_construction) C++17
100 / 100
 3784 ms 28948 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n, k;
vector<pair<ll, ll> > sor;
set<pair<ll, ll> > ck;
vector<ll> mo;

vector<ll> calc(ll r){
    ck.clear();
    vector<ll> res;
    ll ind = 0;
    for (ll i = 0; i < n; i++){
        // cout << sor[i].first << " " << sor[i].second << ": " << endl;
        while (ind < i && sor[i].first - sor[ind].first > r) {
            ck.erase(make_pair(sor[ind].second, sor[ind].first));
            ind++;
        }
        // for (auto x : ck){
        //     cout << x.first << " " << x.second << endl;
        // }
        auto it = ck.lower_bound(make_pair(sor[i].second - r, -4000000001));
        while (res.size() < k && it != ck.end() && it -> first <= sor[i].second + r){
            // cout << it -> first << " " << it -> second << endl;
            ll x1 = (sor[i].first + sor[i].second) / 2, y1 = (sor[i].first - sor[i].second) / 2;
            ll x2 = (it -> first + it -> second) / 2, y2 = (it -> second - it -> first) / 2;
            // cout << x1 << " " << y1 << " " << x2 << " " << y2 << ": " << abs(x1 - x2) + abs(y1 - y2) << endl;
            res.push_back(abs(x1 - x2) + abs(y1 - y2));
            it++;
        }
        ck.insert(make_pair(sor[i].second, sor[i].first));
    }
    return res;
}

int main(){

    cin >> n >> k;
    sor.resize(n);
    for (ll i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        sor[i] = make_pair(a + b, a - b);
    }

    sort (sor.begin(), sor.end());

    ll l = 0, r = 40000000001;
    while (l != r){
        ll mid = (l + r) / 2;
        if (calc(mid).size() >=k) r = mid;
        else l = mid + 1;
    }

    mo = calc(l - 1);

    sort(mo.begin(), mo.end());
    for (ll i = 0; i < k; i++){
        if (i < mo.size()) cout << mo[i] << '\n';
        else cout << l << '\n';
    }

    return 0;
}

Compilation message

road_construction.cpp: In function 'std::vector<long long int> calc(ll)':
road_construction.cpp:25:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   25 |         while (res.size() < k && it != ck.end() && it -> first <= sor[i].second + r){
      |                ~~~~~~~~~~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:53:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   53 |         if (calc(mid).size() >=k) r = mid;
      |             ~~~~~~~~~~~~~~~~~^~~
road_construction.cpp:61:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if (i < mo.size()) cout << mo[i] << '\n';
      |             ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 6800 KB Output is correct
2 Correct 193 ms 6880 KB Output is correct
3 Correct 160 ms 6956 KB Output is correct
4 Correct 184 ms 7028 KB Output is correct
5 Correct 184 ms 5852 KB Output is correct
6 Correct 6 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 23060 KB Output is correct
2 Correct 1375 ms 23068 KB Output is correct
3 Correct 148 ms 6784 KB Output is correct
4 Correct 1289 ms 22844 KB Output is correct
5 Correct 1431 ms 23068 KB Output is correct
6 Correct 1444 ms 23064 KB Output is correct
7 Correct 1422 ms 22360 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3139 ms 19816 KB Output is correct
2 Correct 3076 ms 19756 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1312 ms 22632 KB Output is correct
5 Correct 2311 ms 25128 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3139 ms 19816 KB Output is correct
2 Correct 3076 ms 19756 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1312 ms 22632 KB Output is correct
5 Correct 2311 ms 25128 KB Output is correct
6 Correct 3339 ms 24888 KB Output is correct
7 Correct 3338 ms 24932 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 3285 ms 24916 KB Output is correct
11 Correct 1294 ms 22764 KB Output is correct
12 Correct 2432 ms 25184 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 6800 KB Output is correct
2 Correct 193 ms 6880 KB Output is correct
3 Correct 160 ms 6956 KB Output is correct
4 Correct 184 ms 7028 KB Output is correct
5 Correct 184 ms 5852 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 1377 ms 14120 KB Output is correct
8 Correct 1430 ms 14124 KB Output is correct
9 Correct 158 ms 7020 KB Output is correct
10 Correct 1130 ms 13360 KB Output is correct
11 Correct 898 ms 13328 KB Output is correct
12 Correct 694 ms 14104 KB Output is correct
13 Correct 919 ms 12688 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 6800 KB Output is correct
2 Correct 193 ms 6880 KB Output is correct
3 Correct 160 ms 6956 KB Output is correct
4 Correct 184 ms 7028 KB Output is correct
5 Correct 184 ms 5852 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 1436 ms 23060 KB Output is correct
8 Correct 1375 ms 23068 KB Output is correct
9 Correct 148 ms 6784 KB Output is correct
10 Correct 1289 ms 22844 KB Output is correct
11 Correct 1431 ms 23068 KB Output is correct
12 Correct 1444 ms 23064 KB Output is correct
13 Correct 1422 ms 22360 KB Output is correct
14 Correct 3139 ms 19816 KB Output is correct
15 Correct 3076 ms 19756 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1312 ms 22632 KB Output is correct
18 Correct 2311 ms 25128 KB Output is correct
19 Correct 3339 ms 24888 KB Output is correct
20 Correct 3338 ms 24932 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 3285 ms 24916 KB Output is correct
24 Correct 1294 ms 22764 KB Output is correct
25 Correct 2432 ms 25184 KB Output is correct
26 Correct 1377 ms 14120 KB Output is correct
27 Correct 1430 ms 14124 KB Output is correct
28 Correct 158 ms 7020 KB Output is correct
29 Correct 1130 ms 13360 KB Output is correct
30 Correct 898 ms 13328 KB Output is correct
31 Correct 694 ms 14104 KB Output is correct
32 Correct 919 ms 12688 KB Output is correct
33 Correct 3784 ms 26988 KB Output is correct
34 Correct 3710 ms 26988 KB Output is correct
35 Correct 3115 ms 26964 KB Output is correct
36 Correct 1867 ms 28948 KB Output is correct
37 Correct 1854 ms 28904 KB Output is correct
38 Correct 2275 ms 27200 KB Output is correct