oj.uz

Submission #968614

# Submission time Handle Problem Language Result Execution time Memory
968614 2024-04-23T17:42:23 Z LOLOLO Road Construction (JOI21_road_construction) C++17
100 / 100
 1592 ms 15308 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e5 + 50;
vector <ll> lst;
vector <pair <ll, ll>> point;
int lim;

void solve(ll k) {
    set <pair <ll, ll>> save;
    lst.clear();
    int j = 0; 
    for (int i = 0; i < sz(point); i++) {
        while (point[i].f - point[j].f > k) {
            save.erase({point[j].s, j});
            j++;
        }

        auto it = save.lower_bound({point[i].s - k, -1});
        while (it != save.end()) {
            if (abs(it -> f - point[i].s) > k)
                break;

            lst.pb(max(abs(point[it -> s].s - point[i].s), abs(point[i].f - point[it -> s].f)));
            if (sz(lst) >= lim)
                return;

            it = next(it);
        }

        save.insert({point[i].s, i});
    }
}

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n >> lim;

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        point.pb({x + y, x - y});
    }

    sort(all(point));

    ll l = 0, r = 4e9, m, ans;
    while (l <= r) {
        m = (l + r) / 2;
        solve(m);
        if (sz(lst) >= lim) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    solve(ans - 1);

    while (sz(lst) < lim)
        lst.pb(ans);

    sort(all(lst));

    for (auto x : lst)
        cout << x << '\n';

    return 0;
}

/*
10 10
10 -8
7 2
7 -8
-3 -6
-2 1
-8 6
8 -1
2 4
6 -6
2 -1
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 5148 KB Output is correct
2 Correct 89 ms 5152 KB Output is correct
3 Correct 84 ms 5076 KB Output is correct
4 Correct 83 ms 5144 KB Output is correct
5 Correct 91 ms 3872 KB Output is correct
6 Correct 3 ms 344 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 9400 KB Output is correct
2 Correct 326 ms 9404 KB Output is correct
3 Correct 76 ms 4928 KB Output is correct
4 Correct 246 ms 9184 KB Output is correct
5 Correct 256 ms 9448 KB Output is correct
6 Correct 263 ms 9404 KB Output is correct
7 Correct 240 ms 8856 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 5836 KB Output is correct
2 Correct 257 ms 9432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 109 ms 7492 KB Output is correct
5 Correct 333 ms 9660 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 5836 KB Output is correct
2 Correct 257 ms 9432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 109 ms 7492 KB Output is correct
5 Correct 333 ms 9660 KB Output is correct
6 Correct 378 ms 9380 KB Output is correct
7 Correct 348 ms 9420 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 285 ms 9400 KB Output is correct
11 Correct 95 ms 8404 KB Output is correct
12 Correct 314 ms 9668 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 5148 KB Output is correct
2 Correct 89 ms 5152 KB Output is correct
3 Correct 84 ms 5076 KB Output is correct
4 Correct 83 ms 5144 KB Output is correct
5 Correct 91 ms 3872 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 762 ms 8036 KB Output is correct
8 Correct 754 ms 7968 KB Output is correct
9 Correct 81 ms 5132 KB Output is correct
10 Correct 404 ms 7448 KB Output is correct
11 Correct 242 ms 7276 KB Output is correct
12 Correct 314 ms 8040 KB Output is correct
13 Correct 403 ms 7116 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 5148 KB Output is correct
2 Correct 89 ms 5152 KB Output is correct
3 Correct 84 ms 5076 KB Output is correct
4 Correct 83 ms 5144 KB Output is correct
5 Correct 91 ms 3872 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 320 ms 9400 KB Output is correct
8 Correct 326 ms 9404 KB Output is correct
9 Correct 76 ms 4928 KB Output is correct
10 Correct 246 ms 9184 KB Output is correct
11 Correct 256 ms 9448 KB Output is correct
12 Correct 263 ms 9404 KB Output is correct
13 Correct 240 ms 8856 KB Output is correct
14 Correct 204 ms 5836 KB Output is correct
15 Correct 257 ms 9432 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 109 ms 7492 KB Output is correct
18 Correct 333 ms 9660 KB Output is correct
19 Correct 378 ms 9380 KB Output is correct
20 Correct 348 ms 9420 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 285 ms 9400 KB Output is correct
24 Correct 95 ms 8404 KB Output is correct
25 Correct 314 ms 9668 KB Output is correct
26 Correct 762 ms 8036 KB Output is correct
27 Correct 754 ms 7968 KB Output is correct
28 Correct 81 ms 5132 KB Output is correct
29 Correct 404 ms 7448 KB Output is correct
30 Correct 242 ms 7276 KB Output is correct
31 Correct 314 ms 8040 KB Output is correct
32 Correct 403 ms 7116 KB Output is correct
33 Correct 1592 ms 15256 KB Output is correct
34 Correct 1586 ms 15260 KB Output is correct
35 Correct 1030 ms 14536 KB Output is correct
36 Correct 546 ms 15308 KB Output is correct
37 Correct 525 ms 15256 KB Output is correct
38 Correct 637 ms 13968 KB Output is correct