Submission #1157931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157931		shn	Road Construction (JOI21_road_construction)	C++20	0 / 100	9420 ms	92440 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#define Respaabs1equal2xdoner cin.tie(nullptr)->sync_with_stdio(false);
#define pll pair < long long , long long >
#define len(s) (long long)(s.size())
#define all(x) x.begin(), x.end()
#define int long long
#define pb push_back
#define F first
#define S second
const int N = 75e4 + 77, inf = 1e18 + 77;

int n, k;
int x[N][5], y[N][5], t[N];

inline void rotate(int &a, int &b) {
    int c = a;
    a = a - b;
    b = c + b;
}

void upd(int pos, int val, int size) {
    while (pos <= size) {
        t[pos] += val;
        pos += pos & -pos;
    }
}

int get(int pos) {
    int sum = 0;
    while (pos) {
        sum += t[pos];
        pos -= pos & -pos;
    }
    return sum;
}

bool check(int d) {
    int ans = 0;
    vector<pair<int, int>> events;
    vector<int> coords;
    
    for (int i = 1; i <= n; i++) {
        int a = x[i][0], b = y[i][0];
        x[i][1] = a, y[i][1] = b + d;
        x[i][2] = a + d, y[i][2] = b;
        x[i][3] = a, y[i][3] = b - d;
        x[i][4] = a - d, y[i][4] = b;

        for (int j = 1; j <= 4; j++) rotate(x[i][j], y[i][j]);
        rotate(a, b);
        
        coords.pb(a);
        coords.pb(x[i][1]);
        coords.pb(x[i][2]);

        events.pb({b, 1});
        events.pb({y[i][1], -1});
    }

    sort(all(coords));
    coords.erase(unique(all(coords)), coords.end());

    auto get_comp = [&](int v) {
        return lower_bound(all(coords), v) - coords.begin() + 1;
    };

    vector<pair<int, pair<int, int>>> g;
    for (int i = 1; i <= n; i++) {
        int a = x[i][0], b = y[i][0];
        rotate(a, b);

        int l = get_comp(a), r1 = get_comp(x[i][1]), r2 = get_comp(x[i][2]);
        g.pb({b, {1, l}});
        g.pb({y[i][1], {-1, l}});
        g.pb({b, {2, r1}});
        g.pb({b, {2, r2}});
    }

    sort(all(g));

    int sz = coords.size();
    memset(t, 0, (sz + 5) * sizeof(int));

    for (auto it : g) {
        int type = it.S.F, pos = it.S.S;
        if (type == 1) upd(pos, 1, sz);
        else if (type == -1) upd(pos, -1, sz);
        else ans += get(pos) - 1;
    }

    return (ans < k);
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> x[i][0] >> y[i][0];
    }

    int l = 1, r = 4e9 - 1, res = 4e9;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            l = mid + 1;
        } else {
            res = mid;
            r = mid - 1;
        }
    }
    cout << res << '\n';
}

signed main() {
    Respaabs1equal2xdoner
    int T = 1;
    while (T--) {
        solve();
    }
}

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