Submission #1209389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209389		emptypringlescan	Road Construction (JOI21_road_construction)	C++17	100 / 100	6320 ms	18192 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
long long fenw[500005];
void update(int x, long long v){
	x++;
	for(;x<500005;x+=x&-x) fenw[x]+=v;
}
long long query(int x){
	x++;
	long long ret=0;
	for(;x;x-=x&-x) ret+=fenw[x];
	return ret;
}
int n,k;
pair<long long,long long> arr[250005];
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	vector<long long> disc;
	for(int i=0; i<n; i++){
		long long a,b;
		cin >> a >> b;
		arr[i]={a+b,a-b};
		disc.push_back(a+b);
		disc.push_back(a-b);
	}
	sort(disc.begin(),disc.end());
	disc.erase(unique(disc.begin(),disc.end()),disc.end());
	sort(arr,arr+n);
	long long lo=0,hi=1e13,mid;
	while(lo<hi){
		mid=(lo+hi+1)/2ll;
		long long got=0;
		int cnt=0;
		for(int i=0; i<n; i++){
			while(cnt<i&&arr[cnt].first<arr[i].first-mid){
				int ind=lower_bound(disc.begin(),disc.end(),arr[cnt].second)-disc.begin();
				update(ind,-1);
				cnt++;
			}
			int lb=lower_bound(disc.begin(),disc.end(),arr[i].second-mid)-disc.begin();
			int ub=upper_bound(disc.begin(),disc.end(),arr[i].second+mid)-disc.begin()-1;
			assert(lb<=ub);
			got+=query(ub)-query(lb-1);
			int ind=lower_bound(disc.begin(),disc.end(),arr[i].second)-disc.begin();
			update(ind,1);
		}
		for(;cnt<n;cnt++){
			int ind=lower_bound(disc.begin(),disc.end(),arr[cnt].second)-disc.begin();
			update(ind,-1);
		}
		if(got<k) lo=mid;
		else hi=mid-1;
	}
	int cnt=0;
	set<pair<long long,long long> > s;
	set<pair<long long,long long> >::iterator it;
	vector<long long> ans;
	for(int i=0; i<n; i++){
		while(cnt<i&&arr[cnt].first<arr[i].first-lo){
			s.erase({arr[cnt].second,arr[cnt].first});
			cnt++;
		}
		it=s.lower_bound({arr[i].second-lo,-1e16});
		while(it!=s.end()&&it->first<=arr[i].second+lo){
			ans.push_back(max(abs(arr[i].second-it->first),abs(arr[i].first-it->second)));
			it++;
		}
		s.insert({arr[i].second,arr[i].first});
	}
	while((int)ans.size()<k) ans.push_back(lo+1);
	sort(ans.begin(),ans.end());
	for(auto i:ans) cout << i << '\n';
}

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