Submission #1157865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157865		yf_yusuf	Road Construction (JOI21_road_construction)	C++20	5 / 100	10112 ms	2162688 KiB

road_construction

//```//    YF YUSUF
#define Free_open(File) freopen((File".in"),"r",stdin);freopen((File".out"),"w",stdout);
#define YF ios_base::sync_with_stdio(0);cout.setf(ios::fixed);
#define YUSUF cout.precision(0);cout.tie(0);cin.tie(0);
#include <bits/stdc++.h>
using namespace std;
#ifdef YF_CHECK
	bool Output=1;
	#include "g/debug.h"
	//#include "g/bigint.h"
	//#include "g/text.h"
#else
	bool Output=0;
	#define deb(x...) 42 
#endif
using ll  =  long long;
using ld  =  long double;
using vll =  vector <ll>;
using mll =  map <ll,ll>;
using pll =  pair <ll,ll>;
using vpll=  vector <pll>;
template<class T>T MIN(T&a,T b){a=min(a,b);return a;}
template<class T>T MAX(T&a,T b){a=max(a,b);return a;}
#define revers(a) reverse(all(a))
#define all(a) a.begin(),a.end()
#define sortt(a) sort(all(a))
#define sgr v+v+1,tm+1,tr
#define sgl v+v,tl,tm
#define pb push_back
#define ins insert
#define S second
#define F first
#define int ll
ll BP(ll a,ll b,ll mod=1e9+7){
	if(b==0)return 1;
	ll q=BP(a,b/2,mod);
	return ((q*q)%mod*(b%2?a:1ll))%mod;
}
ll dup(ll a,ll b){return (a+b-1)/b;}
ll f(ll x){return x*(x+1)/2;}
const int mod=998244353;
const int INF=1e18+7;
const int inf=1e9+7;
const int N  =1e6+7;
ll n,k;
pll a[N];
ll dist(pll a,pll b){
	return abs(a.F-b.F)+abs(a.S-b.S);
}
void zhadnik(){
	set<pair<ll,pll>>st;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			st.ins({dist(a[i],a[j]),{i,j}});
		}
	}
	while(k--){
		auto now=*st.begin();
		cout<<now.F<<"\n";
		st.erase(now);
	}
}
ll sz=1;
ll t[N*4];
ll L[N*4];
ll R[N*4];
void up(ll pos,ll v=1,ll tl=0,ll tr=2e9){
	if(tl==tr){
		t[v]++;
	}
	else{
		ll tm=(tl+tr)/2;
		if(pos<=tm){
			if(!L[v])L[v]=++sz;
			up(pos,L[v],tl,tm);
		}
		else{
			if(!R[v])R[v]=++sz;
			up(pos,R[v],tm+1,tr);
		}
		t[v]++;
	}
}
ll get(ll l,ll r,ll v=1,ll tl=0,ll tr=2e9){
	if(l>r)return 0;
	if(l>tr || tl>r)return 0;
	if(l<=tl && tr<=r)return t[v];
	ll tm=(tl+tr)/2;
	ll left=0,right=0;
	if(L[v])left =get(l,r,L[v],tl  ,tm);
	if(R[v])right=get(l,r,R[v],tm+1,tr);
	return left+right;
}
void YF_MAIN(){
	cin>>n>>k;
	set<pll>st;
	bool test=1;
	vll v;
	for(int i=1;i<=n;i++){
		cin>>a[i].F>>a[i].S;
		st.ins({a[i].F,i});
		if(a[i].S)test=0;
	}
	sort(a+1,a+n+1);
	if(!test)zhadnik();
	else{
		for(int i=1;i<=n;i++){
			up(a[i].F+1e9);
		}
		ll l=1,r=2e9,ans=2e9;
		while(l<=r){
			ll m=(l+r)/2;
			ll cnt=0;
			for(int i=1;i<=n;i++){
				cnt+=get(a[i].F-m+1e9,a[i].F+1e9-1);
			}
			if(cnt>=k){
				ans=m;
				r=m-1;
			}
			else l=m+1;
		}
//		cout<<ans<<" ANS\n";
		vll ANS;
		for(int i=1;i<=n;i++){
			if(st.upper_bound({a[i].F-ans-1,0})==st.end())continue;
			pll J=*st.upper_bound({a[i].F-ans-1,0});
			ll j=J.S;
//			cout<<i<<" "<<j<<"\n";
			for(int k=j;k<i;k++){
//				cout<<i<<" "<<k<<" "<<a[i].F<<" "<<a[k].F<<"\n";
				ANS.pb(dist(a[i],a[k]));
			}
		}
		sortt(ANS);
		for(int i=0;i<k;i++){
			cout<<ANS[i]<<" ";
		}
	}
}
bool TECT=0;
bool CASE=0;
bool OUTP=1;
//ll FACT[1],inv[1],FMOD=1e9+7;
//ll PER(ll n,ll k){return FACT[n] *inv[n-k]%FMOD;}
//ll CNK(ll n,ll k){return PER(n,k)*inv[k  ]%FMOD;}
//ll lg[1];
void BEFORE(){
//	return;
//	FACT[0]=inv[0]=1;
//	for(int i=2;i<N;i++){
//		lg[i]=lg[i/2]+1;
//	}
//	for(int i=1;i<=1e6;i++){
//		FACT[i]=FACT[i-1]*i%FMOD;
//		inv[i]=BP(FACT[i],FMOD-2,FMOD);
//	}
}
signed main(){
	if(OUTP){YF YUSUF}
//	Free_open("TEST");
	cout<<(Output ? "\nYF_OUTPUT:\n\n" : "");
	int TEST=1;
	if(TECT)
		cin>>TEST;
	BEFORE();
	for(int T=1;T<=TEST;T++){
		if(CASE)
			cout<<"Case "<<T<<": ";
		YF_MAIN();
		cout<<(T==TEST ? "" : "\n");
	}
	return 0;
} 
//```

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