Submission #916929

#	Time	Username	Problem	Language	Result	Execution time	Memory
916929		makrav	Road Construction (JOI21_road_construction)	C++14	7 / 100	3541 ms	47220 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

struct fenwick {
    int n;
    vector<int> t;
    fenwick() = default;
    fenwick(int n_) {
        n = n_;
        t.assign(n + 1, 0);
    }

    void clear() {
        t.assign(n + 1, 0);
    }

    int sum(int x) {
        int ans = 0;
        for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
            ans += t[i];
        }
        return ans;
    }

    void upd(int pos, int delta) {
        for (int i = pos; i < n; i = i | (i + 1)) {
            t[i] += delta;
        }
    }
};

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));
    f (i, 0, n) {
        posy[ys[i].sc] = i;
        posx[xs[i].sc] = i;
    }

    ll L = -1, R = 4 * 1000ll * 1000ll * 1000ll;
    vector<int> nextx(n), prevx(n), nexty(n), prevy(n);
    vector<vector<int>> evs(n + 1);
    fenwick fw(n + 1);
    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;
        }

        fw.clear();
        for (int i = 0; i < n; i++) {
            evs[prevx[posx[i]]].pb(i);
            evs[nextx[posx[i]] + 1].pb(i);
        }
        //cout << M << '\n';
        vector<int> ans(n);
        f (i, 1, n + 1) {
            fw.upd(posy[xs[i - 1].sc] + 1, 1);
            for (auto& u : evs[i]) {
                if (prevx[posx[u]] == i) {
                    ans[u] += fw.sum(prevy[posy[u]]);
                    ans[u] -= fw.sum(nexty[posy[u]] + 1);
                    //cout << u << ' ' << prevy[posy[u]] << ' ' << nexty[posy[u]] + 1 << ' ' << ans[u] << '\n';
                }
            }
            for (auto& u : evs[i]) {
                if (nextx[posx[u]] + 1 == i) {
                    ans[u] -= fw.sum(prevy[posy[u]]);
                    ans[u] += fw.sum(nexty[posy[u]] + 1);
                    //cout << u << ' ' << prevy[posy[u]] << ' ' << nexty[posy[u]] + 1 << ' ' << ans[u] << '\n';
                }
            }
        }   
        f (i, 0, n + 1) evs[i].clear();
        f (i, 0, n) sm += ans[i] - 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: 7 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35