oj.uz

Submission #899372

# Submission time Handle Problem Language Result Execution time Memory
899372 2024-01-05T22:57:45 Z box Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 114752 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
using namespace std;

#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;
    for (int i = 0; i < N; i++) {
        int l = lower_bound(all(vy), Y[i] - c) - begin(vy);
        int r = upper_bound(all(vy), Y[i] + c) - begin(vy) - 1;
        int d = lower_bound(all(vx), X[i] - c) - begin(vx);
        int u = upper_bound(all(vx), X[i] + c) - begin(vx) - 1;
        int now = qry(tr[u + 1], 0, sz(vy) - 1, l, r) - qry(tr[d], 0, sz(vy) - 1, l, r) - 1;
        num += now;
        if (num > K * 2) return K + 1;
    }
    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 213 ms 35616 KB Output is correct
2 Correct 213 ms 35500 KB Output is correct
3 Correct 205 ms 37836 KB Output is correct
4 Correct 198 ms 37824 KB Output is correct
5 Correct 173 ms 31808 KB Output is correct
6 Correct 10 ms 27228 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4589 ms 108076 KB Output is correct
2 Correct 4515 ms 108080 KB Output is correct
3 Correct 181 ms 37784 KB Output is correct
4 Correct 4014 ms 114752 KB Output is correct
5 Correct 3532 ms 114740 KB Output is correct
6 Correct 3504 ms 114736 KB Output is correct
7 Correct 2892 ms 103724 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5976 ms 104388 KB Output is correct
2 Correct 7459 ms 104896 KB Output is correct
3 Correct 7 ms 27228 KB Output is correct
4 Correct 2493 ms 111556 KB Output is correct
5 Correct 1448 ms 69456 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5976 ms 104388 KB Output is correct
2 Correct 7459 ms 104896 KB Output is correct
3 Correct 7 ms 27228 KB Output is correct
4 Correct 2493 ms 111556 KB Output is correct
5 Correct 1448 ms 69456 KB Output is correct
6 Correct 8616 ms 104260 KB Output is correct
7 Correct 8981 ms 104132 KB Output is correct
8 Correct 6 ms 27228 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 7830 ms 104192 KB Output is correct
11 Correct 2232 ms 111404 KB Output is correct
12 Correct 1631 ms 69344 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 35616 KB Output is correct
2 Correct 213 ms 35500 KB Output is correct
3 Correct 205 ms 37836 KB Output is correct
4 Correct 198 ms 37824 KB Output is correct
5 Correct 173 ms 31808 KB Output is correct
6 Correct 10 ms 27228 KB Output is correct
7 Correct 5093 ms 64120 KB Output is correct
8 Correct 5374 ms 64160 KB Output is correct
9 Correct 201 ms 37824 KB Output is correct
10 Correct 3890 ms 61132 KB Output is correct
11 Correct 1550 ms 62228 KB Output is correct
12 Correct 692 ms 47560 KB Output is correct
13 Correct 747 ms 47820 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 35616 KB Output is correct
2 Correct 213 ms 35500 KB Output is correct
3 Correct 205 ms 37836 KB Output is correct
4 Correct 198 ms 37824 KB Output is correct
5 Correct 173 ms 31808 KB Output is correct
6 Correct 10 ms 27228 KB Output is correct
7 Correct 4589 ms 108076 KB Output is correct
8 Correct 4515 ms 108080 KB Output is correct
9 Correct 181 ms 37784 KB Output is correct
10 Correct 4014 ms 114752 KB Output is correct
11 Correct 3532 ms 114740 KB Output is correct
12 Correct 3504 ms 114736 KB Output is correct
13 Correct 2892 ms 103724 KB Output is correct
14 Correct 5976 ms 104388 KB Output is correct
15 Correct 7459 ms 104896 KB Output is correct
16 Correct 7 ms 27228 KB Output is correct
17 Correct 2493 ms 111556 KB Output is correct
18 Correct 1448 ms 69456 KB Output is correct
19 Correct 8616 ms 104260 KB Output is correct
20 Correct 8981 ms 104132 KB Output is correct
21 Correct 6 ms 27228 KB Output is correct
22 Correct 6 ms 27228 KB Output is correct
23 Correct 7830 ms 104192 KB Output is correct
24 Correct 2232 ms 111404 KB Output is correct
25 Correct 1631 ms 69344 KB Output is correct
26 Correct 5093 ms 64120 KB Output is correct
27 Correct 5374 ms 64160 KB Output is correct
28 Correct 201 ms 37824 KB Output is correct
29 Correct 3890 ms 61132 KB Output is correct
30 Correct 1550 ms 62228 KB Output is correct
31 Correct 692 ms 47560 KB Output is correct
32 Correct 747 ms 47820 KB Output is correct
33 Execution timed out 10087 ms 95832 KB Time limit exceeded
34 Halted 0 ms 0 KB -