Submission #1295110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295110		purplelemon	Road Construction (JOI21_road_construction)	C++20	6 / 100	3323 ms	831144 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define endl '\n'
#define all(x) x.begin(),x.end()

const int N = 3e5;
int n, k;
int cnt[N], fen[N], L[N], R[N];
pair<int,int> nums[N];
vector<int> YS, got;
deque<int> tree[4*N];
vector<pair<int,int>> ans;

void PUSH(int v,int tl,int tr,int ind,int x) {
    if (tr < ind || tl > ind) return;
    tree[v].push_back(x);
    if (tl == tr) return;
    int mid = (tl+tr)/2;
    PUSH(2*v,tl,mid,ind,x);
    PUSH(2*v+1,mid+1,tr,ind,x);
}

void REM(int v,int tl,int tr,int ind) {
    if (tr < ind || tl > ind) return;
    tree[v].pop_front();
    if (tl == tr) return;
    int mid = (tl+tr)/2;
    REM(2*v,tl,mid,ind);
    REM(2*v+1,mid+1,tr,ind);
}

void GRAB(int v,int tl,int tr,int l,int r) {
    if (r < l) return;
    if (tl == l && tr == r) {
        for (int val : tree[v]) {
            got.push_back(val);
        }
        return;
    }
    int mid = (tl+tr)/2;
    GRAB(2*v,tl,mid,l,min(r,mid));
    GRAB(2*v+1,mid+1,tr,max(l,mid+1),r);
}

void SET(int i,int x) {
    int y = x;
    x = x-cnt[i];
    cnt[i] = y;
    while (i < N) {
        fen[i] += x;
        i |= (i+1);
    }
}

int PREF(int r) {
    int ans = 0;
    while (r >= 0) {
        ans += fen[r];
        r = (r&(r+1))-1;
    }
    return ans;
}

int SUM(int l,int r) {
    return PREF(r)-PREF(l-1);
}

bool F(int a) {
    int l = 0;
    int r = 0;
    for (int i = 0;i < YS.size();i++) {
        while (YS[i]-YS[l] > a) {
            l++;
        }
        while (r+1 < YS.size() && YS[r+1]-YS[i] <= a) {
            r++;
        }
        L[i] = l;
        R[i] = r;
    }
    for (int i = 0;i < YS.size();i++) {
        SET(i,0);
    }
    l = 1;
    int sm = 0;
    for (int i = 1;i <= n;i++) {
        while (nums[i].first-nums[l].first > a) {
            int compy = lower_bound(all(YS),nums[l].second)-YS.begin();
            SET(compy,cnt[compy]-1);
            l++;
        }
        int compy = lower_bound(all(YS),nums[i].second)-YS.begin();
        sm += SUM(L[compy],R[compy]);
        SET(compy,cnt[compy]+1);
    }
    return (sm >= k);
}

void FIND(int a) {
    int l = 0;
    int r = 0;
    for (int i = 0;i < YS.size();i++) {
        while (YS[i]-YS[l] > a) {
            l++;
        }
        while (r+1 < YS.size() && YS[r+1]-YS[i] <= a) {
            r++;
        }
        L[i] = l;
        R[i] = r;
    }
    l = 1;
    for (int i = 1;i <= n;i++) {
        while (nums[i].first-nums[l].first > a) {
            int compy = lower_bound(all(YS),nums[l].second)-YS.begin();
            REM(1,0,YS.size()-1,compy);
            l++;
        }
        int compy = lower_bound(all(YS),nums[i].second)-YS.begin();
        got.clear();
        GRAB(1,0,YS.size()-1,L[compy],R[compy]);
        for (int val : got) {
            ans.push_back({val,i});
        }
        PUSH(1,0,YS.size()-1,compy,i);
    }
}

int dis(int i,int j){
    return max(abs(nums[i].first-nums[j].first),abs(nums[i].second-nums[j].second));
}
bool cmp(pair<int,int> a,pair<int,int> b) {
    return (dis(a.first,a.second)<dis(b.first,b.second));
}

/*
4 3
0 0
1 2
2 1
3 2
*/

void solve() {
    cin >> n >> k;
    for (int i = 1;i <= n;i++) {
        cin >> nums[i].first >> nums[i].second;
        nums[i] = {nums[i].first+nums[i].second,nums[i].second-nums[i].first};
    }
    sort(nums+1,nums+n+1);
    for (int i = 1;i <= n;i++) {
        YS.push_back(nums[i].second);
    }
    sort(all(YS));
    YS.resize(unique(all(YS))-YS.begin());
    int l = 0;
    int r = 2e9;
    while (r-l > 1) {
        int mid = (l+r)/2;
        if (F(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    FIND(r);
    sort(all(ans),cmp);
    for (int i = 0;i < k;i++) {
        cout << dis(ans[i].first,ans[i].second) << '\n';
    }
}


int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc = 1;
    //cin >> tc;
    while(tc--) {
        solve();
    }
}

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