oj.uz

Submission #899373

# Submission time Handle Problem Language Result Execution time Memory
899373 2024-01-05T23:03:58 Z box Road Construction (JOI21_road_construction) C++17
100 / 100
 4687 ms 76028 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#ifdef LOCAL
#define bug(x) cerr << "L" << __LINE__ << " | " << #x << " => " << x << endl
#else
#define bug(x)
#define cerr if (0) cerr
#endif

#define ar array
#define sz(v) int(std::size(v))
#define all(v) std::begin(v), std::end(v)
using i64 = long long;
using vi = vector<int>;
using pi = pair<int, int>;

const int MAXN = 25e4;

int N, K;
i64 X[MAXN], Y[MAXN], x[MAXN], y[MAXN];
vector<i64> vx, vy;
vi at_x[MAXN];
// int tr[MAXN + 1];

/*
const int MAXS = MAXN * 20;

int lc[MAXS], rc[MAXS], sum[MAXS];
int tt;

void inc(int &k, int l, int r, int i) {
    ++tt;
    lc[tt] = lc[k], rc[tt] = rc[k], sum[tt] = sum[k] + 1;
    k = tt;
    if (l < r) {
        int m = (l + r) / 2;
        i <= m ? inc(lc[k], l, m, i) : inc(rc[k], m + 1, r, i);
    }
}

int qry(int k, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) return sum[k];
    int m = (l + r) / 2, x = 0;
    if (ql <= m && lc[k]) x += qry(lc[k], l, m, ql, qr);
    if (qr > m && rc[k]) x += qry(rc[k], m + 1, r, ql, qr);
    return x;
}
*/

int get_count(i64 c) {
    int num = 0;
    vector<tuple<i64, int, int>> events;
    for (int i = 0; i < N; i++) {
        events.push_back({X[i] - c, 0, i});
        events.push_back({X[i], 1, i});
        events.push_back({X[i] + c, 2, i});
    }
    sort(all(events));
    ordered_set<pair<i64, int>> os;
    for (auto [x, t, i] : events)
        if (t == 0) os.insert({Y[i], i});
        else if (t == 2) os.erase({Y[i], i});
        else {
            num += os.order_of_key({Y[i] + c, MAXN}) - os.order_of_key({Y[i] - c, 0}) - 1;
            if (num > K * 2) return K + 1;
        }
    // assert(num % 2 == 0);
    return num / 2;
}

vector<i64> ans;
set<i64> open;
vi add[MAXN], del[MAXN];
set<pair<i64, int>> active;

void add_ans(i64 x) {
    if (open.count(x)) open.erase(x);
    else open.insert(x), ans.push_back(x);
}

i64 dist(int i, int j) {
    return max(abs(i64(X[i]) - X[j]), abs(i64(Y[i]) - Y[j]));
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
        tie(X[i], Y[i]) = pi(X[i] - Y[i], X[i] + Y[i]);
    }
    vx = vector(X, X + N), vy = vector(Y, Y + N);
    sort(all(vx)), vx.erase(unique(all(vx)), end(vx));
    sort(all(vy)), vy.erase(unique(all(vy)), end(vy));
    for (int i = 0; i < N; i++) {
        x[i] = lower_bound(all(vx), X[i]) - begin(vx);
        y[i] = lower_bound(all(vy), Y[i]) - begin(vy);
        at_x[x[i]].push_back(i);
    }
    /*
    for (int i = 0; i < sz(vx); i++) {
        tr[i + 1] = tr[i];
        for (int j : at_x[i]) inc(tr[i + 1], 0, sz(vy) - 1, y[j]);
    }
    */
    i64 low = 0, hi = 4e9;
    while (low < hi) {
        i64 m = (low + hi) / 2 + 1;
        get_count(m) <= K ? low = m : hi = m - 1;
    }
    i64 c = low;
    for (int i = 0; i < N; i++) {
        int d = lower_bound(all(vx), X[i] - c) - begin(vx);
        int u = upper_bound(all(vx), X[i] + c) - begin(vx) - 1;
        add[d].push_back(i);
        del[u].push_back(i);
    }
    for (int i = 0; i < sz(vx); i++) {
        for (int j : add[i]) active.insert({Y[j], j});
        for (int j : at_x[i])
            for (auto it = active.lower_bound({Y[j] - c, -1}); it != end(active) && it->first <= Y[j] + c; ++it)
                if (j != it->second) add_ans(dist(j, it->second));
        for (int j : del[i]) active.erase({Y[j], j});
    }
    // for (auto x : ans) bug(x);
    // assert(get_count(c) == sz(ans));
    sort(all(ans));
    while (sz(ans) < K) ans.push_back(c + 1);
    for (auto x : ans) cout << x << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 33468 KB Output is correct
2 Correct 204 ms 33552 KB Output is correct
3 Correct 217 ms 35804 KB Output is correct
4 Correct 194 ms 35612 KB Output is correct
5 Correct 167 ms 29580 KB Output is correct
6 Correct 18 ms 25412 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2974 ms 67400 KB Output is correct
2 Correct 2960 ms 66936 KB Output is correct
3 Correct 170 ms 35520 KB Output is correct
4 Correct 2960 ms 67780 KB Output is correct
5 Correct 3242 ms 67272 KB Output is correct
6 Correct 3164 ms 66412 KB Output is correct
7 Correct 2919 ms 67108 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2589 ms 70816 KB Output is correct
2 Correct 2636 ms 70900 KB Output is correct
3 Correct 5 ms 25176 KB Output is correct
4 Correct 2994 ms 67152 KB Output is correct
5 Correct 3559 ms 65916 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2589 ms 70816 KB Output is correct
2 Correct 2636 ms 70900 KB Output is correct
3 Correct 5 ms 25176 KB Output is correct
4 Correct 2994 ms 67152 KB Output is correct
5 Correct 3559 ms 65916 KB Output is correct
6 Correct 2836 ms 69864 KB Output is correct
7 Correct 2850 ms 69760 KB Output is correct
8 Correct 5 ms 25176 KB Output is correct
9 Correct 5 ms 25184 KB Output is correct
10 Correct 2798 ms 70732 KB Output is correct
11 Correct 3034 ms 66980 KB Output is correct
12 Correct 3532 ms 63152 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 33468 KB Output is correct
2 Correct 204 ms 33552 KB Output is correct
3 Correct 217 ms 35804 KB Output is correct
4 Correct 194 ms 35612 KB Output is correct
5 Correct 167 ms 29580 KB Output is correct
6 Correct 18 ms 25412 KB Output is correct
7 Correct 1957 ms 45212 KB Output is correct
8 Correct 1959 ms 46532 KB Output is correct
9 Correct 191 ms 35772 KB Output is correct
10 Correct 1644 ms 45404 KB Output is correct
11 Correct 1108 ms 44948 KB Output is correct
12 Correct 1826 ms 44344 KB Output is correct
13 Correct 1743 ms 42304 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 33468 KB Output is correct
2 Correct 204 ms 33552 KB Output is correct
3 Correct 217 ms 35804 KB Output is correct
4 Correct 194 ms 35612 KB Output is correct
5 Correct 167 ms 29580 KB Output is correct
6 Correct 18 ms 25412 KB Output is correct
7 Correct 2974 ms 67400 KB Output is correct
8 Correct 2960 ms 66936 KB Output is correct
9 Correct 170 ms 35520 KB Output is correct
10 Correct 2960 ms 67780 KB Output is correct
11 Correct 3242 ms 67272 KB Output is correct
12 Correct 3164 ms 66412 KB Output is correct
13 Correct 2919 ms 67108 KB Output is correct
14 Correct 2589 ms 70816 KB Output is correct
15 Correct 2636 ms 70900 KB Output is correct
16 Correct 5 ms 25176 KB Output is correct
17 Correct 2994 ms 67152 KB Output is correct
18 Correct 3559 ms 65916 KB Output is correct
19 Correct 2836 ms 69864 KB Output is correct
20 Correct 2850 ms 69760 KB Output is correct
21 Correct 5 ms 25176 KB Output is correct
22 Correct 5 ms 25184 KB Output is correct
23 Correct 2798 ms 70732 KB Output is correct
24 Correct 3034 ms 66980 KB Output is correct
25 Correct 3532 ms 63152 KB Output is correct
26 Correct 1957 ms 45212 KB Output is correct
27 Correct 1959 ms 46532 KB Output is correct
28 Correct 191 ms 35772 KB Output is correct
29 Correct 1644 ms 45404 KB Output is correct
30 Correct 1108 ms 44948 KB Output is correct
31 Correct 1826 ms 44344 KB Output is correct
32 Correct 1743 ms 42304 KB Output is correct
33 Correct 4687 ms 70424 KB Output is correct
34 Correct 4647 ms 76028 KB Output is correct
35 Correct 3720 ms 73360 KB Output is correct
36 Correct 4399 ms 73836 KB Output is correct
37 Correct 4166 ms 73312 KB Output is correct
38 Correct 4003 ms 68992 KB Output is correct