Submission #961750

#	Time	Username	Problem	Language	Result	Execution time	Memory
961750		LCJLY	Road Construction (JOI21_road_construction)	C++14	100 / 100	8803 ms	50596 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<int,pii>pi2;

int fw[1000005];
int n,k;

void upd(int x, int y){
	while(x<1000005){
		fw[x]+=y;
		x+=x&(-x);
	}
}

int sum(int x){	
	int counter=0;
	while(x>0){
		counter+=fw[x];
		x-=x&(-x);
	}	
	return counter;
}

void rangeUpd(int x, int y, int c){
	x=max(x,1LL);
	y=min(y,1000000LL);
	upd(x,c);
	upd(y+1,-c);
}

void solve(){
	cin >> n >> k;
	pii arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x].first >> arr[x].second;
		int a=arr[x].first+arr[x].second;
		int b=arr[x].first-arr[x].second;
		arr[x].first=a;
		arr[x].second=b;
		//show2(a,a,b,b);
	}
	
	sort(arr,arr+n);
	
	int l=0;
	int r=4e9;
	int mid;
	int best=r;
	while(l<=r){
		//show2(l,l,r,r);
		mid=(l+r)/2;
		
		int counter=0;
		
		vector<array<int,4>>v;
		vector<int>dis;
		for(int x=0;x<n;x++){
			int a=arr[x].first;
			int b=arr[x].second;
			v.push_back({a-mid,0,b-mid,b+mid});
			v.push_back({a,1,b,b});
			dis.push_back(b-mid);
			dis.push_back(b+mid);
			dis.push_back(b);
		}
		sort(v.begin(),v.end());
		//for(auto it:v){
			//cout << it[0] << " " << it[1] << " " << it[2] << " " << it[3] << endl;
		//}
		sort(dis.begin(),dis.end());
		dis.resize(unique(dis.begin(),dis.end())-dis.begin());
		int ptr=0;
		memset(fw,0,sizeof(fw));
		int sz=v.size();
		
		//show4(dis,dis);
		
		for(int x=0;x<sz;x++){
			v[x][2]=lower_bound(dis.begin(),dis.end(),v[x][2])-dis.begin()+1;
			v[x][3]=lower_bound(dis.begin(),dis.end(),v[x][3])-dis.begin()+1;
			//show3(v[x][1],v[x][1],v[x][2],v[x][2],v[x][3],v[x][3]);
			while(ptr<sz&&v[x][0]-2*mid>v[ptr][0]){
				if(v[ptr][1]==0){
					rangeUpd(v[ptr][2],v[ptr][3],-1);
				}
				ptr++;
			}
			
			if(v[x][1]==0){
				rangeUpd(v[x][2],v[x][3],1);
			}
			else{
				counter+=sum(v[x][2]);
			}
			//show(counter,counter);
		}
		
		counter=(counter-n)/2;
		//show(counter,counter);
		
		if(counter>=k){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	//show(best,best);
	
	vector<int>ans;
	multiset<pii>se;
	int ptr2=0;
	for(int x=0;x<n;x++){
		while(ptr2<n&&arr[ptr2].first<arr[x].first-best){
			se.erase(se.find({arr[ptr2].second,arr[ptr2].first}));
			ptr2++;
		}
		
		//show3(x,x,arr[x].first,arr[x].first,arr[x].second,arr[x].second);
		auto rt=se.lower_bound({arr[x].second,1e15});
		auto cur=rt;
		while(cur!=se.end()){
			pii hold=*cur;
			if(hold.first>arr[x].second+best) break;
			ans.push_back(max(abs(hold.first-arr[x].second),abs(hold.second-arr[x].first)));
			//show2(hold.first,hold.first,hold.second,hold.second);
			cur++;
		}
		cur=rt;
		while(cur!=se.begin()){
			cur--;
			pii hold=*cur;
			if(hold.first<arr[x].second-best) break;
			ans.push_back(max(abs(hold.first-arr[x].second),abs(hold.second-arr[x].first)));
			//show2(hold.first,hold.first,hold.second,hold.second);
		}
		se.insert({arr[x].second,arr[x].first});
	}
	
	sort(ans.begin(),ans.end());
	for(int x=0;x<k;x++){
		cout << ans[x] << "\n";
	}
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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