oj.uz

Submission #916921

# Submission time Handle Problem Language Result Execution time Memory
916921 2024-01-26T19:04:05 Z makrav Road Construction (JOI21_road_construction) C++14
0 / 100
 10000 ms 86816 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vei;
typedef vector<vei> vevei;

#define all(a) (a).begin(), (a).end()
#define sz(a) (int) a.size()
#define con cout << "NO\n"
#define coe cout << "YES\n";
#define str string
#define pb push_back
#define ff first
#define sc second
#define ss second
#define pii pair<int, int>
#define mxe max_element
#define mne min_element
#define stf shrink_to_fit
#define f(i, l, r) for (int i = (l); i < (r); i++)
#define double ld

const int MAXS = 10000000;
int S[MAXS];
pair<int, int> nxt[MAXS];
int siz = 1;

struct node {
    int sm;
    node* l = nullptr, *r = nullptr;
    node() = default;
    node(int sm_) {
        sm = sm_;
    }
};

int upd(int v, int tl, int tr, int p, int val) {
    if (tl + 1 == tr) {
        S[siz] = S[v] + val;
        nxt[siz] = {-1, -1};
        siz++;
        return siz - 1;
    }
    int ind = siz++;
    int tm = (tl + tr) / 2;
    if (p < tm) {
        if (nxt[v].ff == -1) {
            nxt[v].ff = siz++;
            S[siz - 1] = 0;
            nxt[siz - 1] = {-1, -1};
        }
        auto rs = upd(nxt[v].ff, tl, tm, p, val);
        nxt[ind].ff = rs;
        nxt[ind].sc = nxt[v].sc;
        S[ind] = S[rs];
        if (nxt[ind].sc != -1) S[ind] += S[nxt[ind].sc];
    }
    else {
        if (nxt[v].sc == -1) {
            nxt[v].sc = siz++;
            S[siz - 1] = 0;
            nxt[siz - 1] = {-1, -1};
        }
        auto rs = upd(nxt[v].sc, tm, tr, p, val);
        nxt[ind].ff = nxt[v].ff;
        nxt[ind].sc = rs;
        S[ind] = S[rs];
        if (nxt[ind].ff != -1) S[ind] += S[nxt[ind].ff];
    }
    return ind;
}

int get(int v, int tl, int tr, int l, int r) {
    if (v == -1) return 0;
    if (l <= tl && tr <= r) return S[v];
    if (tr <= l || tl >= r) return 0;
    int tm = (tl + tr) / 2;
    return get(nxt[v].ff, tl, tm, l, r) + get(nxt[v].sc, tm, tr, l, r);
}

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

    int n, k; cin >> n >> k;
    vector<pair<ll, ll>> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].ff >> a[i].sc;

    vector<pair<ll, ll>> b(n), xs(n), ys(n);
    for (int i = 0; i < n; i++) {
        b[i] = {a[i].ff - a[i].sc, a[i].ff + a[i].sc};
        xs[i] = {b[i].ff, i};
        ys[i] = {b[i].sc, i};
    }   
    vector<int> posx(n), posy(n);
    sort(all(xs));
    sort(all(ys));
    vector<int> roots(n + 1);
    roots[0] = 0;
    S[0] = 0;
    nxt[0] = {-1, -1};
    f (i, 0, n) {
        posy[ys[i].sc] = i;
        posx[xs[i].sc] = i;
    }

    for (int i = 0; i < n; i++) {
        roots[i + 1] = upd(roots[i], 0, n, posy[i], 1);
    }
    //return 0;

    auto getrect = [&](ll lx, ll rx, ll ly, ll ry) {
        int li = lx, ri = rx, lj = ly, rj = ry;
        return get(roots[ri + 1], 0, n, lj, rj + 1) - get(roots[li], 0, n, lj, rj + 1);
    };

    ll L = -1, R = 4 * 1000ll * 1000ll * 1000ll;
    vector<int> nextx(n), prevx(n), nexty(n), prevy(n);
    while (R - L > 1) {
        ll M = (L + R) / 2;
        ll sm = 0;

        int ind = 0;
        f (i, 0, n) {
            while (ind + 1 < n && xs[ind + 1].ff - xs[i].ff <= M) ind++;
            nextx[i] = ind;
        }
        ind = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            while (ind - 1 >= 0 && xs[i].ff - xs[ind - 1].ff <= M) ind--;
            prevx[i] = ind;
        }
        ind = 0;
        f(i, 0, n) {
            while (ind + 1 < n && ys[ind + 1].ff - ys[i].ff <= M) ind++;
            nexty[i] = ind;
        }
        ind = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            while (ind - 1 >= 0 && ys[i].ff - ys[ind - 1].ff <= M) ind--;
            prevy[i] = ind;
        }
        
        for (int i = 0; i < n; i++) {
            sm += getrect(prevx[posx[i]], nextx[posx[i]], prevy[posy[i]], nexty[posy[i]]) - 1;
        }
        if (sm / 2 >= k) R = M;
        else L = M;
    }
    cout << R << '\n';

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10075 ms 86816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10050 ms 86684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10050 ms 86684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -