제출 #1292067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292067		danghuyro	Road Construction (JOI21_road_construction)	C++20	100 / 100	2860 ms	27700 KiB

road_construction

#include <bits/stdc++.h>
#include <ctime>
#include <random>
#define fu(i,a,b) for(int i = a; i < b; i++)
#define fd(i,a,b) for(int i = a; i >= b; i--)
#define pb push_back
#define ll long long
#define fi first
#define se second
#define bit(x,y) ((x >> y)&1)
#define MASK(x) (1 << x)
#define ALL(x) (x).begin(), (x).end()
#define vi pair<ll,ll>
#define vvl vector<vector<ll>>
#define vvvi pair<ll,pair<ll,pair<ll,ll>>>
#define HIGH_MIN(x,y) (a[x] > a[y] ? y : x)
using namespace std;
const ll MAXN = 5e5+2;
const ll MAXC = 1e6+5 ;
const ll base = 31;
const ll MOD = 1e9+7;
const ll LG = 20;
const ll BS = 548;
const ll dx[] = {0,1,0,-1};
const ll dy[] = {-1,0,1,0};
const ll inf = 2e9;
bool minimize(ll& a,const ll& b){ if(a > b){ a = b; return true; } else return false;}
bool maximize(ll& a,const ll& b){ if(a < b){ a = b; return true; } else return false;}
void add(ll& a,const ll& b){ a += b; if(a >= MOD) a -= MOD; }
ll sub(ll a,ll b){ ll r = a - b + MOD; if(r >= MOD) r -= MOD; return r;}
ll n,k,a[MAXN],b[MAXN];
vi c[MAXN];
vector<ll> ans;
ll dist(ll i,ll j){
    return max(abs(c[i].fi-c[j].fi),abs(c[i].se-c[j].se));
}
ll check(ll x){
    set<vi> st; ans.clear();
    ll j = 1;
    fu(i,1,n+1){
        while(!st.empty() && c[j].fi < c[i].fi - x){
            st.erase(make_pair(c[j].se,j));
            j++;
        }
        auto it = st.upper_bound(make_pair(c[i].se-x,-inf));
        while(it != st.end() && ans.size() < k && it->fi <= c[i].se + x){
            ans.emplace_back(dist(i,it->se));
            it = next(it);
        }
//        if(ans.size() == k) break;
        st.emplace(c[i].se,i);
    }
    return ans.size();
}
void solve(){
    cin >> n >> k;
    fu(i,1,n+1){
        cin >> a[i] >> b[i];
        c[i] = {a[i]+b[i],a[i]-b[i]};
    }
    sort(c+1,c+n+1);
    ll l = 0, r = 10000000000,dd = -1;
    while(l <= r){
        ll mid = l+r >> 1;
//        cout << l << ' ' << r << '\n';
        if(check(mid) < k){
            dd = mid;
            l = mid+1;
        }
        else r = mid-1;
    }
    check(dd);
    while(ans.size() < k) ans.push_back(dd+1);
    sort(ALL(ans));
    for(ll it: ans) cout << it << '\n';
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	freopen("code.inp","r",stdin);
//	freopen("code.out","w",stdout);
    ll tt = 1;
	while(tt--) solve();
	return 0;
}

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