Submission #1294908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294908		Hamed_Ghaffari	Road Construction (JOI21_road_construction)	C++20	38 / 100	10084 ms	33228 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define X first
#define Y second
#define mid ((l+r)>>1)
#define lc id<<1
#define rc lc|1
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())

const int MXN = 250005;

int n, k;
pii a[MXN];
vector<ll> cmp;

inline int GI(ll x) { return lower_bound(all(cmp), x)-cmp.begin(); }

int N;
pii seg[MXN<<2];
set<int> st[MXN];
pii operator+(pii x, pii y) {
    return pii(x.X+y.X, x.X ? x.Y : y.Y);
}
void build(int l=0, int r=N, int id=1) {
    if(r-l == 1) {
        seg[id] = {0, l};
        st[l].clear();
        return;
    }
    build(l, mid, lc);
    build(mid, r, rc);
    seg[id] = seg[lc] + seg[rc];
}
void upd(int p, int x, int y, int l=0, int r=N, int id=1) {
    if(r-l == 1) {
        seg[id].X += x;
        seg[id].Y = l;
        if(x==1) st[l].insert(y);
        else st[l].erase(y);
        return;
    }
    p<mid ? upd(p, x, y, l, mid, lc) : upd(p, x, y, mid, r, rc);
    seg[id] = seg[lc] + seg[rc];
}
pii get(int s, int e, int l=0, int r=N, int id=1) {
    if(s>=r || l>=e) return {0, l};
    if(s<=l && r<=e) return seg[id];
    return get(s, e, l, mid, lc) + get(s, e, mid, r, rc);
}

ll check(ll m) {
    build();
    ll res = 0;
    int p=1;  
    for(int i=1; i<=n; i++) {
        while(a[i].X+a[i].Y - (a[p].X+a[p].Y) > m) {
            upd(GI(a[p].X-a[p].Y), -1, p);
            p++;
        }
        res += get(GI(a[i].X-a[i].Y-m), GI(a[i].X-a[i].Y+m+1)).X;
        upd(GI(a[i].X-a[i].Y), 1, i);
    }
    return res;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i].X >> a[i].Y, cmp.push_back(a[i].X-a[i].Y);
    sort(a+1, a+n+1, [&](pii x, pii y) { 
        return x.X+x.Y < y.X+y.Y;
    });
    sort(all(cmp));
    cmp.resize(unique(all(cmp))-cmp.begin());
    N = SZ(cmp);
    ll l=0, r=4e9;
    while(r-l>1)
        (check(mid)>=k ? r : l) = mid;
    int c = k-check(l);
    build();
    vector<ll> ans;
    for(int i=0; i<c; i++) ans.push_back(r);
    int p=1;
    for(int i=1; i<=n; i++) {
        while(a[i].X+a[i].Y - (a[p].X+a[p].Y) > l) {
            upd(GI(a[p].X-a[p].Y), -1, p);
            p++;
        }
        vector<int> vec = {i};
        while(1) {
            pii x = get(GI(a[i].X-a[i].Y-l), GI(a[i].X-a[i].Y+l+1));
            if(!x.X) break;
            int w = *st[x.Y].begin();
            ans.push_back(1ll*abs(a[i].X-a[w].X) + abs(a[i].Y-a[w].Y));
            upd(GI(a[w].X-a[w].Y), -1, w);
            vec.push_back(w);
        }
        for(int j : vec)
            upd(GI(a[j].X-a[j].Y), 1, j);
    }
    sort(all(ans));
    for(ll i : ans) cout << i << '\n';
    return 0;
}

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