oj.uz

Submission #899369

# Submission time Handle Problem Language Result Execution time Memory
899369 2024-01-05T22:46:24 Z box Road Construction (JOI21_road_construction) C++17
45 / 100
 10000 ms 117772 KB 
#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;
        assert(0 <= l && l < sz(vy));
        assert(0 <= r && r < sz(vy));
        int d = lower_bound(all(vx), X[i] - c) - begin(vx);
        int u = upper_bound(all(vx), X[i] + c) - begin(vx) - 1;
        assert(0 <= d && d < sz(vx));
        assert(0 <= u && u < sz(vx));
        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;
    }
    // bug(c);
    // bug(num);
    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 = 5e9;
    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;
        assert(0 <= d && d < sz(vx));
        assert(0 <= u && u < sz(vx));
        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));
    while (sz(ans) < K) ans.push_back(c + 1);
    sort(all(ans));
    for (auto x : ans) cout << x << '\n';
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:124:15: warning: unused variable 'x' [-Wunused-variable]
  124 |     for (auto x : ans) bug(x);
      |               ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 35524 KB Output is correct
2 Correct 194 ms 35520 KB Output is correct
3 Correct 203 ms 38328 KB Output is correct
4 Correct 184 ms 37820 KB Output is correct
5 Correct 160 ms 31808 KB Output is correct
6 Correct 11 ms 27484 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4994 ms 108080 KB Output is correct
2 Correct 5200 ms 108084 KB Output is correct
3 Correct 163 ms 37800 KB Output is correct
4 Correct 4353 ms 117656 KB Output is correct
5 Correct 4235 ms 117680 KB Output is correct
6 Correct 3955 ms 117772 KB Output is correct
7 Correct 2972 ms 106896 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7902 ms 104384 KB Output is correct
2 Correct 8055 ms 105156 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 2228 ms 114552 KB Output is correct
5 Correct 2587 ms 74848 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7902 ms 104384 KB Output is correct
2 Correct 8055 ms 105156 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 2228 ms 114552 KB Output is correct
5 Correct 2587 ms 74848 KB Output is correct
6 Correct 9167 ms 109732 KB Output is correct
7 Execution timed out 10034 ms 109220 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 35524 KB Output is correct
2 Correct 194 ms 35520 KB Output is correct
3 Correct 203 ms 38328 KB Output is correct
4 Correct 184 ms 37820 KB Output is correct
5 Correct 160 ms 31808 KB Output is correct
6 Correct 11 ms 27484 KB Output is correct
7 Correct 6141 ms 66164 KB Output is correct
8 Correct 5314 ms 66052 KB Output is correct
9 Correct 183 ms 37824 KB Output is correct
10 Correct 4033 ms 63484 KB Output is correct
11 Correct 1875 ms 64532 KB Output is correct
12 Correct 774 ms 49656 KB Output is correct
13 Correct 700 ms 49792 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 35524 KB Output is correct
2 Correct 194 ms 35520 KB Output is correct
3 Correct 203 ms 38328 KB Output is correct
4 Correct 184 ms 37820 KB Output is correct
5 Correct 160 ms 31808 KB Output is correct
6 Correct 11 ms 27484 KB Output is correct
7 Correct 4994 ms 108080 KB Output is correct
8 Correct 5200 ms 108084 KB Output is correct
9 Correct 163 ms 37800 KB Output is correct
10 Correct 4353 ms 117656 KB Output is correct
11 Correct 4235 ms 117680 KB Output is correct
12 Correct 3955 ms 117772 KB Output is correct
13 Correct 2972 ms 106896 KB Output is correct
14 Correct 7902 ms 104384 KB Output is correct
15 Correct 8055 ms 105156 KB Output is correct
16 Correct 5 ms 27228 KB Output is correct
17 Correct 2228 ms 114552 KB Output is correct
18 Correct 2587 ms 74848 KB Output is correct
19 Correct 9167 ms 109732 KB Output is correct
20 Execution timed out 10034 ms 109220 KB Time limit exceeded
21 Halted 0 ms 0 KB -