Submission #916946

#	Time	Username	Problem	Language	Result	Execution time	Memory
916946		makrav	Road Construction (JOI21_road_construction)	C++14	100 / 100	4745 ms	133136 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;
        }
    }
};

vector<pair<int, int>> pts;

struct mst {
    int n;
    vector<pair<int, int>> a;
    vector<vector<pair<int, int>>> t;
    mst() = default;
    mst(int n_, vector<pair<int, int>> a_) {
        n = n_;
        a = a_;
        t.resize(4 * n);
        build(1, 0, n);
    }

    void build(int v, int tl, int tr) {
        if (tl + 1 == tr) {
            t[v] = {a[tl]};
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm, tr);
        t[v].resize(tr - tl);
        merge(all(t[v * 2]), all(t[v * 2 + 1]), t[v].begin());
    }

    void mark(int v, int tl, int tr, int l, int r, int l1, int r1, int I) {
        if (l <= tl && tr <= r) {
            int lf, rg;
            {
                int L = -1, R = sz(t[v]);
                while (R - L > 1) {
                    int M = (L + R) / 2;
                    if (t[v][M].ff >= l1) R = M;
                    else L = M;
                }
                lf = R;
            }
            {
                int L = -1, R = sz(t[v]);
                while (R - L > 1) {
                    int M = (L + R) / 2;
                    if (t[v][M].ff <= r1) L = M;
                    else R = M;
                }
                rg = L;
            }
            for (int j = lf; j <= rg; j++) {
                pts.pb({t[v][j].sc, I});
            }
            return;
        }
        if (tr <= l || tl >= r) return;
        int tm = (tl + tr) / 2;
        mark(v * 2, tl, tm, l, r, l1, r1, I);
        mark(v * 2 + 1, tm, tr, l, r, l1, r1, I);
    }
};

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);
        }
        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);
                }
            }
            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);
                }
            }
        }   
        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';

    auto dist = [&](int i, int j) {
        return abs(a[i].ff - a[j].ff) + abs(a[i].sc - a[j].sc);
    };

    vector<pair<int, int>> tomst;
    f (i, 0, n) {
        //cout << xs[i].sc << ' ' << b[xs[i].sc].sc << '\n';
        tomst.pb({posy[xs[i].sc], xs[i].sc});
    }
    mst MS(n, tomst);
    ll M = L;
    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;
    }

    f (i, 0, n) {
        //cout << prevx[posx[i]] << ' ' << nextx[posx[i]] + 1 <<  '\n';
        MS.mark(1, 0, n, prevx[posx[i]], nextx[posx[i]] + 1, prevy[posy[i]], nexty[posy[i]], i);
    }
    vector<ll> DS;
    for (auto &u : pts) {
        if (u.ff < u.sc && dist(u.ff, u.sc) > 0) {
            DS.pb(dist(u.ff, u.sc));
        }
    }

    sort(all(DS));
    f (i, 0, sz(DS)) cout << DS[i] << '\n';

    f (i, 0, k - sz(DS)) cout << R << '\n';

    return 0;
}

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