Submission #1283217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283217		tung04885	Road Construction (JOI21_road_construction)	C++20	33 / 100	261 ms	5620 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 250200
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) a.begin(),a.end()

const ll inf=2e18+412009;

struct POINT
{
    int x,y;
};

bool cmp(POINT a,POINT b)
{
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

int n,k;
POINT a[MAX];

void nhap()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        a[i]={x+y,x-y};
    }
}

bool check(ll m)
{
    multiset<ll> st;
    int T1=1;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        while(a[i].x-a[T1].x>m) st.erase(st.find(a[T1++].y));
        for(auto it=st.lower_bound(a[i].y-m);it!=st.end()&&*it<=a[i].y+m;it++) if(++cnt>=k) return 1;
        st.insert(a[i].y);
    }
    return 0;
}

void solve()
{
    nhap();
    sort(a+1,a+n+1,cmp);
    ll ans=4e9;
    ll l=0,r=4e9;
    while(l<=r)
    {
        ll mid=l+r>>1;
        if(check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    ans--;
    multiset<pll> st;
    vector<ll> res;
    int T1=1;
    for(int i=1;i<=n;i++)
    {
        while(a[i].x-a[T1].x>ans)
        {
            st.erase({a[T1].y,a[T1].x});
            T1++;
        }
        for(auto it=st.lower_bound({a[i].y-ans,-inf});it!=st.end();it++)
        {
            pll tmp=*it;
            if(tmp.fi>a[i].y+ans) break;
            res.push_back(max(abs(a[i].x-tmp.se),abs(a[i].y-tmp.fi)));
        }
        st.insert({a[i].y,a[i].x});
    }
    sort(all(res));
    for(ll val:res) cout<<val<<'\n';
    k-=(int)res.size();
    while(k--) cout<<ans+1<<'\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    solve();
    return 0;
}

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