Submission #1149570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149570		Perl32	Road Construction (JOI21_road_construction)	C++17	5 / 100	10157 ms	1639524 KiB

road_construction

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template<typename T> using normal_queue = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
struct WT {
    vector<vector<ll>> t, pref;
    vector<T> srt;
    ll sz;

    WT() {}
    WT(vector<T>& a) {
        srt = a;
        sort(srt.begin(), srt.end());
        srt.resize(unique(srt.begin(), srt.end()) - srt.begin());
        sz = 1;
        while (sz < (ll) srt.size()) sz <<= 1;
        t.resize(sz << 1);
        pref.resize(sz << 1);
        t[1] = a;
        for (auto& x : t[1]) x = lower_bound(srt.begin(), srt.end(), x) - srt.begin();
        build(1, 0, srt.size());
    }

    void build(ll x, ll lx, ll rx) {
        if (lx + 1 == rx) return;
        ll m = (lx + rx) >> 1;
        pref[x].resize(t[x].size() + 1);
        for (ll i = 0; i < (ll) t[x].size(); ++i) {
            bool le = (t[x][i] < m);
            pref[x][i + 1] = pref[x][i] + le;
            if (le) {
                t[x << 1].push_back(t[x][i]);
            } else {
                t[x << 1 | 1].push_back(t[x][i]);
            }
        }
        build(x << 1, lx, m);
        build(x << 1 | 1, m, rx);
    }

    ll le(ll l, ll r, ll v, ll x, ll lx, ll rx) {
        if (lx >= v) return 0;
        if (rx <= v) return r - l;
        ll m = (lx + rx) >> 1, lb = pref[x][l], rb = pref[x][r];
        return le(lb, rb, v, x << 1, lx, m) + le(l - lb, r - rb, v, x << 1 | 1, m, rx);
    }

    ll le(ll l, ll r, T v) { // counting elements lower than v in [l, r)
        v = lower_bound(srt.begin(), srt.end(), v) - srt.begin();
        return le(l, r, v, 1, 0, srt.size());
    }
};

struct Info {
    vector<ll> x, y;
    WT<ll> tt;

    Info() = default;
    Info(const vector<ll>& _x, const vector<ll>& _y) : x(_x), y(_y) {
        if (x.size()) tt = WT<ll>(y);
    }

    ll get(ll lx, ll ly, ll rx, ll ry) { // [lx, ly] : [rx, ry]
        lx = lower_bound(x.begin(), x.end(), lx) - x.begin();
        rx = upper_bound(x.begin(), x.end(), rx) - x.begin();
        return tt.le(lx, rx, ry + 1) - tt.le(lx, rx, ly);
    }
};

Info operator+(const Info& a, const Info& b) {
    vector<ll> nx, ny;
    for (ll l = 0, r = 0; l < (ll) a.x.size() || r < (ll) b.x.size();) {
        if (l < (ll) a.x.size() && r < (ll) b.x.size()) {
            if (pair{a.x[l], a.y[l]} < pair{b.x[r], b.y[r]}) {
                nx.push_back(a.x[l]);
                ny.push_back(a.y[l++]);
            } else {
                nx.push_back(b.x[r]);
                ny.push_back(b.y[r++]);
            }
        } else if (l < (ll) a.x.size()) {
            nx.push_back(a.x[l]);
            ny.push_back(a.y[l++]);
        } else {
            nx.push_back(b.x[r]);
            ny.push_back(b.y[r++]);
        }
    }
    Info res(nx, ny);
    return res;
}

struct ST {
    vector<Info> t;
    ll sz;

    ST(vector<pair<ll, ll>>& a) {
        sz = 1;
        while (sz < (ll) a.size()) sz <<= 1;
        t.resize(sz << 1);
        for (ll i = 0; i < (ll) a.size(); ++i) t[i + sz] = Info({a[i].first}, {a[i].second});
        for (ll i = sz - 1; i > 0; --i) {
            t[i] = t[i << 1] + t[i << 1 | 1];
        }
    }

    ll get(ll l, ll r, ll lx, ll ly, ll rx, ll ry) {
        l += sz; r += sz;
        ll res = 0;
        while (l < r) {
            if (l & 1) res += t[l++].get(lx, ly, rx, ry);
            if (r & 1) res += t[--r].get(lx, ly, rx, ry);
            l >>= 1; r >>= 1;
        }
        return res;
    }
};

const ll inf = 0x3f3f3f3f3f3f;

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, k;
    cin >> n >> k;
    vector<pair<ll, ll>> a(n);
    for (auto& c : a) {
        ll x, y;
        cin >> x >> y;
        c = {x + y, x - y};
    }
    ST tt(a);
    auto counting = [&](ll i, ll m) {
        ll lx = a[i].first - m, rx = a[i].first + m;
        ll ly = a[i].second - m, ry = a[i].second + m;
        return tt.get(i, n, lx, ly, rx, ry);
    };
    vector<ll> cnt(n, 1);
    auto solve = [&](ll i) {
        ll lx = -1, rx = inf;
        while (lx + 1 < rx) {
            ll m = (lx + rx) >> 1;
            if (counting(i, m) <= cnt[i]) {
                lx = m;
            } else {
                rx = m;
            }
        }
        return rx;
    };
    normal_queue<pair<ll, ll>> pq;
    for (ll i = 0; i < n; ++i) pq.emplace(solve(i), i);
    while (k--) {
        auto [d, j] = pq.top(); pq.pop();
        cnt[j]++;
        cout << d << '\n';
        if (cnt[j] != n - j) pq.emplace(solve(j), j);
    }
}

/*

 */

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