oj.uz

Submission #553120

# Submission time Handle Problem Language Result Execution time Memory
553120 2022-04-24T17:13:11 Z jesus_coconut Road Construction (JOI21_road_construction) C++17
100 / 100
 2542 ms 13572 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define F first
#define S second
#define all(a) begin(a), end(a)

using namespace std;
using namespace __gnu_pbds;
using ll = long long;

using pii = pair<ll, ll>;

using oset = tree<pii, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;


int n, k;
vector<pii> v;

oset s;

void add(int t) {
    s.insert({v[t].S, t});
}

void rm(int t) {
    s.erase({v[t].S, t});
}

ll cnt(ll y, ll dist) {
    return s.order_of_key({y + dist, INT_MAX}) - s.order_of_key({y - dist, INT_MIN});
}

void load() {
    cin >> n >> k;
    v.resize(n);
    for (auto &[a, b] : v) {
        ll ta, tb;
        cin >> ta >> tb;
        a = ta - tb;
        b = ta + tb;
    }
    sort(all(v));
}

ll solve(ll dist) {
    s.clear();
    int prev = 0;
    ll ret = 0;
    for (int i = 0; i < n; ++i) {
        while (prev < n && v[prev].F < v[i].F - dist) {
            rm(prev++);
        }
        ret += cnt(v[i].S, dist);
        if (ret >= k) return ret;
        add(i);
    }
    return ret;
}

vector<ll> ans;

void construct(ll dist) {
    set<pair<ll, int>> s;
    int prev = 0;
    for (int i = 0; i < n; ++i) {
        while (prev < n && v[prev].F < v[i].F - dist) {
            s.erase({v[prev].S, prev});
            prev++;
        }
        for (auto it = s.lower_bound({v[i].S - dist, INT_MIN}); it != s.upper_bound({v[i].S + dist, INT_MAX}); ++it) {
            ans.push_back(max(abs(v[i].F - v[it->S].F), abs(v[i].S - v[it->S].S)));
        }
        s.insert({v[i].S, i});
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    load();
    ll lo = 1, hi = 4ll * 1e9 + 100;
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (solve(mid) < k) {
            lo = mid + 1;
        } else hi = mid;
    }
    construct(lo - 1);
    sort(all(ans));
    ans.resize(k, lo);
    for (auto a : ans) cout << a << '\n';


    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5044 KB Output is correct
2 Correct 58 ms 5044 KB Output is correct
3 Correct 49 ms 5092 KB Output is correct
4 Correct 50 ms 5068 KB Output is correct
5 Correct 52 ms 3896 KB Output is correct
6 Correct 4 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 10748 KB Output is correct
2 Correct 389 ms 10660 KB Output is correct
3 Correct 44 ms 4920 KB Output is correct
4 Correct 290 ms 10368 KB Output is correct
5 Correct 298 ms 10596 KB Output is correct
6 Correct 291 ms 10596 KB Output is correct
7 Correct 247 ms 10008 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 9292 KB Output is correct
2 Correct 335 ms 9292 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 164 ms 7052 KB Output is correct
5 Correct 568 ms 9560 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 9292 KB Output is correct
2 Correct 335 ms 9292 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 164 ms 7052 KB Output is correct
5 Correct 568 ms 9560 KB Output is correct
6 Correct 537 ms 9224 KB Output is correct
7 Correct 480 ms 9292 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 395 ms 9220 KB Output is correct
11 Correct 153 ms 7172 KB Output is correct
12 Correct 614 ms 9592 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5044 KB Output is correct
2 Correct 58 ms 5044 KB Output is correct
3 Correct 49 ms 5092 KB Output is correct
4 Correct 50 ms 5068 KB Output is correct
5 Correct 52 ms 3896 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 1120 ms 8040 KB Output is correct
8 Correct 1087 ms 8060 KB Output is correct
9 Correct 48 ms 5048 KB Output is correct
10 Correct 654 ms 7320 KB Output is correct
11 Correct 202 ms 7160 KB Output is correct
12 Correct 536 ms 7928 KB Output is correct
13 Correct 541 ms 6760 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5044 KB Output is correct
2 Correct 58 ms 5044 KB Output is correct
3 Correct 49 ms 5092 KB Output is correct
4 Correct 50 ms 5068 KB Output is correct
5 Correct 52 ms 3896 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 430 ms 10748 KB Output is correct
8 Correct 389 ms 10660 KB Output is correct
9 Correct 44 ms 4920 KB Output is correct
10 Correct 290 ms 10368 KB Output is correct
11 Correct 298 ms 10596 KB Output is correct
12 Correct 291 ms 10596 KB Output is correct
13 Correct 247 ms 10008 KB Output is correct
14 Correct 243 ms 9292 KB Output is correct
15 Correct 335 ms 9292 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 164 ms 7052 KB Output is correct
18 Correct 568 ms 9560 KB Output is correct
19 Correct 537 ms 9224 KB Output is correct
20 Correct 480 ms 9292 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 320 KB Output is correct
23 Correct 395 ms 9220 KB Output is correct
24 Correct 153 ms 7172 KB Output is correct
25 Correct 614 ms 9592 KB Output is correct
26 Correct 1120 ms 8040 KB Output is correct
27 Correct 1087 ms 8060 KB Output is correct
28 Correct 48 ms 5048 KB Output is correct
29 Correct 654 ms 7320 KB Output is correct
30 Correct 202 ms 7160 KB Output is correct
31 Correct 536 ms 7928 KB Output is correct
32 Correct 541 ms 6760 KB Output is correct
33 Correct 2504 ms 13364 KB Output is correct
34 Correct 2542 ms 13464 KB Output is correct
35 Correct 1243 ms 12608 KB Output is correct
36 Correct 927 ms 13568 KB Output is correct
37 Correct 914 ms 13572 KB Output is correct
38 Correct 955 ms 12212 KB Output is correct