Submission #916896

#	Time	Username	Problem	Language	Result	Execution time	Memory
916896		makrav	Road Construction (JOI21_road_construction)	C++14	0 / 100	10038 ms	175956 KiB

road_construction

#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
//#define int ll

//const int MAXS = 4500000;
//int S[MAXS];


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

node* upd(node* root, int tl, int tr, int p, int val) {
    if (tl + 1 == tr) {
        node *nw = new node(root->sm + val);
        return nw;
    }
    node* nw = new node(0);
    int tm = (tl + tr) / 2;
    if (p < tm) {
        if (root->l == nullptr) {
            node* nwl = new node(0);
            root->l = nwl;
        }
        auto rs = upd(root->l, tl, tm, p, val);
        nw->l = rs;
        nw->r = root->r;
        nw->sm = rs->sm;
        if (nw->r != nullptr) nw->sm += nw->r->sm;
    }
    else {
        if (root->r == nullptr) {
            root->r = new node(0);
        }
        auto rs = upd(root->r, tm, tr, p, val);
        nw->l = root->l;
        nw->r = rs;
        nw->sm = rs->sm;
        if (nw->l != nullptr) nw->sm += nw->l->sm;
    }
    return nw;
}

int get(node* root, int tl, int tr, int l, int r) {
    if (root == nullptr) return 0;
    if (l <= tl && tr <= r) return root->sm;
    if (tr <= l || tl >= r) return 0;
    int tm = (tl + tr) / 2;
    return get(root->l, tl, tm, l, r) + get(root->r, 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<int, int>> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].ff >> a[i].sc;

    vector<pair<int, int>> 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<node*> roots(n + 1);
    roots[0] = new node(0);
    f (i, 0, n) {
        posy[ys[i].sc] = i;
    }
    for (int i = 0; i < n; i++) {
        roots[i + 1] = upd(roots[i], 0, n, posy[i], 1);
    }

    auto getrect = [&](ll lx, ll rx, ll ly, ll ry) {
        int li, ri, lj, rj;
        {
            int L = -1, R = n;
            while (R - L > 1) {
                int M = (L + R) / 2;
                if (xs[M].ff >= lx) R = M;
                else L = M;
            }
            li = R;
        }
        {
            int L = -1, R = n;
            while (R - L > 1) {
                int M = (L + R) / 2;
                if (xs[M].ff <= rx) L = M;
                else R = M;
            }
            ri = L;
        }
        {
            int L = -1, R = n;
            while (R - L > 1) {
                int M = (L + R) / 2;
                if (ys[M].ff <= ry) L = M;
                else R = M;
            }
            rj = L;
        }
        {
            int L = -1, R = n;
            while (R - L > 1) {
                int M = (L + R) / 2;
                if (ys[M].ff >= ly) R = M;
                else L = M;
            }
            lj = R;
        }
        return get(roots[ri + 1], 0, n, lj, rj + 1) - get(roots[li], 0, n, lj, rj + 1);
    };

    ll L = -1, R = 4000000000ll;
    while (R - L > 1) {
        ll M = (L + R) / 2;
        ll sm = 0;
        for (int i = 0; i < n; i++) {
            sm += getrect(b[i].ff - M, b[i].ff + M, b[i].sc - M, b[i].sc + M) - 1;
        }
        if (sm / 2 >= k) R = M;
        else L = M;
    }
    cout << R << '\n';

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35