oj.uz

Submission #396396

# Submission time Handle Problem Language Result Execution time Memory
396396 2021-04-29T23:29:58 Z 4fecta Road Construction (JOI21_road_construction) C++17
100 / 100
 9340 ms 38104 KB 
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 750005;

int n, k, x, y, bit[MN];
pii a[MN];

void upd(int x, int val) {
    for (int i = x; i < MN; i += i & -i) bit[i] += val;
}

int qry(int x) {
    int ret = 0;
    for (int i = x; i > 0; i -= i & -i) ret += bit[i];
    return ret;
}

int cost(pii p, pii q) {
    return max(abs(p.f - q.f), abs(p.s - q.s));
}

int get(vector<int> &v, int num) {
    int lo = 0, hi = v.size() - 1, mid;
    while (lo <= hi) {
        mid = (lo + hi) >> 1;
        if (v[mid] == num) return mid + 1;
        else if (v[mid] < num) lo = mid + 1;
        else hi = mid - 1;
    }
    abort();
    return -1;
}

int count(int d) {
    int ret = 0;
    memset(bit, 0, sizeof(bit));
    vector<int> ys;
    for (int i = 1; i <= n; i++) {
        ys.push_back(a[i].s);
        ys.push_back(a[i].s - d);
        ys.push_back(a[i].s + d);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    int id = 1;
    for (int i = 1; i <= n; i++) {
        while (a[i].f - a[id].f > d) upd(get(ys, a[id].s), -1), id++;
        ret += qry(get(ys, a[i].s + d)) - qry(get(ys, a[i].s - d) - 1);
        //printf("lol %lld %lld\n", mp[a[i].s + d], mp[a[i].s - d]);
        if (ret >= k) return ret;
        upd(get(ys, a[i].s), 1);
    }
    return ret;
}

void get_ans(int d) {
    vector<int> out;
    set<pii> s;
    vector<int> ys;
    for (int i = 1; i <= n; i++) {
        ys.push_back(a[i].s);
        ys.push_back(a[i].s - d);
        ys.push_back(a[i].s + d);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    int id = 1;
    for (int i = 1; i <= n; i++) {
        while (a[i].f - a[id].f > d) s.erase({get(ys, a[id].s), id}), id++;
        auto it = s.lower_bound({get(ys, a[i].s - d), 0});
        int mx = get(ys, a[i].s + d);
        while (1) {
            if (it == s.end()) break;
            pii cur = *it;
            if (cur.f > mx) break;
            out.push_back(cost(a[i], a[cur.s]));
            it++;
        }
        s.insert({get(ys, a[i].s), i});
    }
    sort(out.begin(), out.end());
    for (int i = 0; i < k; i++) printf("%lld\n", out[i]);
}

int32_t main() {
    boost();

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        a[i] = {x + y, x - y};
        //printf("%lld %lld\n", a[i].f, a[i].s);
    }
    sort(a + 1, a + n + 1);
    int lo = 1, hi = 1e10, mid;
    while (lo < hi) {
        mid = (lo + hi) >> 1;
        if (count(mid) >= k) hi = mid;
        else lo = mid + 1;
    }
    //printf("cnt %lld\n", count(2));
    //printf("%lld\n", lo);
    get_ans(lo);

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10852 KB Output is correct
2 Correct 98 ms 10956 KB Output is correct
3 Correct 78 ms 10936 KB Output is correct
4 Correct 78 ms 10952 KB Output is correct
5 Correct 85 ms 9776 KB Output is correct
6 Correct 23 ms 6220 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2632 ms 25304 KB Output is correct
2 Correct 2768 ms 25336 KB Output is correct
3 Correct 78 ms 10836 KB Output is correct
4 Correct 2363 ms 27636 KB Output is correct
5 Correct 2199 ms 29248 KB Output is correct
6 Correct 2126 ms 29388 KB Output is correct
7 Correct 1953 ms 27224 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4623 ms 24228 KB Output is correct
2 Correct 5410 ms 24212 KB Output is correct
3 Correct 14 ms 6092 KB Output is correct
4 Correct 1693 ms 24252 KB Output is correct
5 Correct 2606 ms 28056 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4623 ms 24228 KB Output is correct
2 Correct 5410 ms 24212 KB Output is correct
3 Correct 14 ms 6092 KB Output is correct
4 Correct 1693 ms 24252 KB Output is correct
5 Correct 2606 ms 28056 KB Output is correct
6 Correct 5862 ms 24348 KB Output is correct
7 Correct 5805 ms 24244 KB Output is correct
8 Correct 13 ms 6092 KB Output is correct
9 Correct 15 ms 6192 KB Output is correct
10 Correct 5631 ms 24448 KB Output is correct
11 Correct 1695 ms 24304 KB Output is correct
12 Correct 2571 ms 24420 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10852 KB Output is correct
2 Correct 98 ms 10956 KB Output is correct
3 Correct 78 ms 10936 KB Output is correct
4 Correct 78 ms 10952 KB Output is correct
5 Correct 85 ms 9776 KB Output is correct
6 Correct 23 ms 6220 KB Output is correct
7 Correct 2890 ms 18184 KB Output is correct
8 Correct 2871 ms 18096 KB Output is correct
9 Correct 79 ms 11096 KB Output is correct
10 Correct 2368 ms 17428 KB Output is correct
11 Correct 2017 ms 17576 KB Output is correct
12 Correct 1066 ms 21420 KB Output is correct
13 Correct 1178 ms 18920 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10852 KB Output is correct
2 Correct 98 ms 10956 KB Output is correct
3 Correct 78 ms 10936 KB Output is correct
4 Correct 78 ms 10952 KB Output is correct
5 Correct 85 ms 9776 KB Output is correct
6 Correct 23 ms 6220 KB Output is correct
7 Correct 2632 ms 25304 KB Output is correct
8 Correct 2768 ms 25336 KB Output is correct
9 Correct 78 ms 10836 KB Output is correct
10 Correct 2363 ms 27636 KB Output is correct
11 Correct 2199 ms 29248 KB Output is correct
12 Correct 2126 ms 29388 KB Output is correct
13 Correct 1953 ms 27224 KB Output is correct
14 Correct 4623 ms 24228 KB Output is correct
15 Correct 5410 ms 24212 KB Output is correct
16 Correct 14 ms 6092 KB Output is correct
17 Correct 1693 ms 24252 KB Output is correct
18 Correct 2606 ms 28056 KB Output is correct
19 Correct 5862 ms 24348 KB Output is correct
20 Correct 5805 ms 24244 KB Output is correct
21 Correct 13 ms 6092 KB Output is correct
22 Correct 15 ms 6192 KB Output is correct
23 Correct 5631 ms 24448 KB Output is correct
24 Correct 1695 ms 24304 KB Output is correct
25 Correct 2571 ms 24420 KB Output is correct
26 Correct 2890 ms 18184 KB Output is correct
27 Correct 2871 ms 18096 KB Output is correct
28 Correct 79 ms 11096 KB Output is correct
29 Correct 2368 ms 17428 KB Output is correct
30 Correct 2017 ms 17576 KB Output is correct
31 Correct 1066 ms 21420 KB Output is correct
32 Correct 1178 ms 18920 KB Output is correct
33 Correct 9213 ms 26224 KB Output is correct
34 Correct 9340 ms 26248 KB Output is correct
35 Correct 7520 ms 25364 KB Output is correct
36 Correct 2518 ms 37924 KB Output is correct
37 Correct 2438 ms 38104 KB Output is correct
38 Correct 2817 ms 27964 KB Output is correct