Submission #47945295

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> du;
typedef tuple<ll,ll,ll> tri;
#define INF (long long)1e18
#define mod 998244353
#define eps 1e-10
#define N 2000000
#define MAXC 30
ll n,k,x[100005],y[100005],r[100005];
map<ll,ll>cx,cy;
deque<du>a,b;
bool check(ll x){
    ll res=0;
    while(!a.empty())
        a.pop_back();
    while(!b.empty())
        b.pop_back();
    for(auto tem:cx)
        a.push_back(tem);
    for(auto tem:cy)
        b.push_back(tem);
    while(a.back().first-a.front().first>x){
        ll dif=a.back().first-a.front().first-x;
        //cout<<a.front().first<<" "<<a.back().first<<endl;
        if(a.front().second<=a.back().second){
            ll dx=a[1].first-a[0].first;
            if(dx>=dif)
                res+=dif*a[0].second,a[0].first+=dif;
            else{
                res+=dx*a[0].second;
                ll tem=a[0].second;
                a.pop_front();
                a[0].second+=tem;
            }
        }
        else{
            ll dx=a[a.size()-1].first-a[a.size()-2].first;
            if(dx>=dif)
                res+=dif*a[a.size()-1].second,a[a.size()-1].first-=dif;
            else{
                res+=dx*a.back().second;
                ll tem=a.back().second;
                a.pop_back();
                a.back().second+=tem;
            }
        }
    }
    while(b.back().first-b.front().first>x){
        ll dif=b.back().first-b.front().first-x;
        if(b.front().second<=b.back().second){
            ll dx=b[1].first-b[0].first;
            if(dx>=dif)
                res+=dif*b[0].second,b[0].first+=dif;
            else{
                res+=dx*b[0].second;
                ll tem=b[0].second;
                b.pop_front();
                b[0].second+=tem;
            }
        }
        else{
            ll dx=b[b.size()-1].first-b[b.size()-2].first;
            if(dx>=dif)
                res+=dif*b[b.size()-1].second,b[b.size()-1].first-=dif;
            else{
                res+=dx*b[b.size()-1].second;
                ll tem=b[b.size()-1].second;
                b.pop_back();
                b[b.size()-1].second+=tem;
            }
        }
    }
    /*cout<<"case="<<x<<endl;
    cout<<a.front().first<<" "<<a.back().first<<endl;
    cout<<b.front().first<<" "<<b.back().first<<endl;*/
    return res<=k;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	cout.tie(0);
    sort(a.begin(),a.end());
    cin>>n>>k;
    cx.clear(),cy.clear();
    for(ll i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        cx[x[i]]++;
        cy[y[i]]++;
    }
    ll l=0,r=1e9,mid,ans;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))
            ans=mid,r=mid-1;
        else
            l=mid+1;
    }
    cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result