Submission #1232665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232665		Mans21	Road Construction (JOI21_road_construction)	C++20	65 / 100	10098 ms	502716 KiB

road_construction

#include <bits/stdc++.h>
#define ent '\n'
#define int long long

using namespace std;

const int maxn = 250'012;

set<pair<int, int>> s[maxn * 4];
int x[maxn], y[maxn];
vector<pair<int, int>> ans;
int n, k;

struct slow_tree {

    void upd(int v, int tl, int tr, int pos, int y) {
        s[v].insert({y,  pos});
        if(tl == tr) {
            return;
        }

        int mid = (tl + tr) >> 1;
        if(pos <= mid) {
            upd(v * 2, tl, mid, pos, y);
        }
        else {
            upd(v * 2 + 1, mid + 1, tr, pos, y);
        }
    }

    void add(int v, int tl, int tr, int lx, int rx, int ly, int ry, int i) {
        if(tl > rx || lx > tr) return;
        if(tl >= lx && tr <= rx) {
            pair<int, int> cur = {ly, 0};
            while((int)ans.size() <= k) {
                auto it = s[v].upper_bound(cur);
                if(it == s[v].end() || it -> first > ry) return;
                ans.push_back({i, it -> second});
                cur = *it;
            }
            return;
        }

        int mid = (tl + tr) >> 1;
        add(v * 2, tl, mid, lx, rx, ly, ry, i);
        add(v * 2 + 1, mid + 1, tr, lx, rx, ly, ry, i);
    }

    bool check(int d) {
        for(int i = 1; i <= n * 4; i++) {
            s[i].clear();
        }
        ans.clear();

        for(int i = 1; i <= n; i++) {
            int pos = i;
            for(int l = 1, r = i - 1; l <= r;) {
                int mid = (l + r) >> 1;
                if(x[i] - x[mid] <= d) {
                    pos = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            add(1, 1, n, pos, i, y[i] - d, y[i] + d, i);
            upd(1, 1, n, i, y[i]);
            if(ans.size() >= k) return true;
        }

        return ans.size() >= k;
    }
} ft;

struct fenwick {
    vector<int> t;

    fenwick() {
        t.clear();
    }

    void resize(int n) {
        t = vector<int> (n, 0);
    }

    void clear() {
        for(int i = 0; i < t.size(); i++) {
            t[i] = 0;
        }
    }

    void upd(int i, int x) {
        for(; i < t.size(); i |= (i + 1)) {
            t[i] += x;
        }
    }

    int get(int i) {
        int ans = 0;
        for(; i >= 0; i = (i & (i + 1)) - 1) {
            ans += t[i];
        }
        return ans;
    }
} t[maxn * 4];

vector<int> g[maxn * 4];

void build(int v, int tl, int tr) {
    for(int i = tl; i <= tr; i++) {
        g[v].push_back(y[i]);
    }
    sort(g[v].begin(), g[v].end());
    g[v].resize(unique(g[v].begin(), g[v].end()) - g[v].begin());
    t[v].resize((int)g[v].size());

    if(tl == tr) return;

    int mid = (tl + tr) >> 1;
    build(v * 2, tl, mid);
    build(v * 2 + 1, mid + 1, tr);
}

void upd(int v, int tl, int tr, int pos, int y) {
    t[v].upd(lower_bound(g[v].begin(), g[v].end(), y) - g[v].begin(), 1);
    if(tl == tr) return;

    int mid = (tl + tr) >> 1;
    if(pos <= mid) {
        upd(v * 2, tl, mid, pos, y);
    }
    else {
        upd(v * 2 + 1, mid + 1, tr, pos, y);
    }
}

int get(int v, int tl, int tr, int l, int r, int ly, int ry) {
    if(tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) {
        return t[v].get((int)(upper_bound(g[v].begin(), g[v].end(), ry) - g[v].begin()) - 1) - t[v].get((int)(lower_bound(g[v].begin(), g[v].end(), ly) - g[v].begin()) - 1);
    }

    int mid = (tl + tr) >> 1;
    return get(v * 2, tl, mid, l, r, ly, ry) + get(v * 2 + 1, mid + 1, tr, l, r, ly, ry);
}

bool check(int d) {
    for(int i = 1; i <= n * 4; i++) {
        t[i].clear();
    }

    int val = 0;
    for(int i = 1; i <= n; i++) {
        int pos = i;
        for(int l = 1, r = i - 1; l <= r;) {
            int mid = (l + r) >> 1;
            if(x[i] - x[mid] <= d) {
                pos = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        val += get(1, 1, n, pos, i, y[i] - d, y[i] + d);
        upd(1, 1, n, i, y[i]);
        if(val >= k) return true;
    }

    return val >= k;
}

void solve() {
    cin >> n >> k;
    vector<pair<int, int>> cur;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        x[i] += y[i];
        y[i] = x[i] - 2 * y[i];
        cur.push_back({x[i], y[i]});
    }

    sort(cur.begin(), cur.end());

    for(int i = 1; i <= n; i++) {
        x[i] = cur[i - 1].first, y[i] = cur[i - 1].second;
    }

    build(1, 1, n);

    int val = -1;
    for(int l = 0, r = 1e10; l <= r;) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            val = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }

    vector<int> v;
    ft.check(val - 1);
    for(auto [i, j] : ans) {
        v.push_back(max(abs(x[i] - x[j]), abs(y[i] - y[j])));
    }
    sort(v.begin(), v.end());
    while(v.size() < k) {
        v.push_back(val);
    }

    for(int x : v) {
        cout << x << ent;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
}

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