Submission #619113

#	Time	Username	Problem	Language	Result	Execution time	Memory
619113		tqbfjotld	Road Construction (JOI21_road_construction)	C++14	100 / 100	5473 ms	33164 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> yvs;
vector<int> xvs;

int fenw[250005];

void upd(int pos, int v){
	pos++;
	while (pos<250005){
		fenw[pos]+=v;
		pos += pos&-pos;
	}
}

int qu(int pos){
	pos++;
	int ans = 0;
	while (pos>0){
		ans += fenw[pos];
		pos -= pos&-pos;
	}
	return ans;
}

int origX[250005];
int origY[250005];
int nX[250005];
int nY[250005];
vector<pair<pair<int,int>,int>> pts;

int lb(int v){
	return lower_bound(yvs.begin(),yvs.end(),v)-yvs.begin();
}
int ub(int v){
	return upper_bound(yvs.begin(),yvs.end(),v)-yvs.begin();
}

int check(int dist){
	for (int x = 0; x<250005; x++) fenw[x] = 0;
	int c = 0;
	int ans = 0;
	for (auto x : pts){
		while (c<pts.size() && pts[c].first.first<=x.first.first+dist){
			upd(lb(pts[c].first.second),1);
			c++;
		}
		upd(lb(x.first.second),-1);
		ans += qu(ub(x.first.second+dist)-1)-qu(lb(x.first.second-dist)-1);
	}
	return ans;
}

vector<pair<int,int> > getall(int dist){
	int c = 0;
	vector<pair<int,int> > ans;
	set<pair<int,int> > stuff;
	for (auto x : pts){
		while (c<pts.size() && pts[c].first.first<=x.first.first+dist){
			stuff.insert({pts[c].first.second,pts[c].second});
			//printf("ins %lld\n",c);
			c++;
		}
		stuff.erase({x.first.second,x.second});
		//printf("er %lld\n",x.second);
		for (auto it = stuff.lower_bound({x.first.second-dist,-1}); (it!=stuff.end()) && (*it).first<=x.first.second+dist; it++){
			ans.push_back({x.second,(*it).second});
			assert(x.second!=(*it).second);
		}
	}
	return ans;
}

int md(pair<int,int> x){
	return abs(origX[x.first]-origX[x.second])+abs(origY[x.first]-origY[x.second]);
}

bool cmp(pair<int,int> a,pair<int,int>b){
	return md(a)<md(b);
}


main(){
	int n,K;
	scanf("%lld%lld",&n,&K);
	for (int x = 0; x<n; x++){
		scanf("%lld%lld",&origX[x],&origY[x]);
		nX[x] = origX[x]+origY[x];
		nY[x] = origY[x]-origX[x];
		pts.push_back({{nX[x],nY[x]},x});
		yvs.push_back(nY[x]);
	}
	sort(pts.begin(),pts.end());
	sort(yvs.begin(),yvs.end());
	
	int l = 0;
	int r = 4000000000LL;
	while (l+1<r){
		int mid = (l+r)/2;
		if (check(mid)>=K){
			r = mid;
		}
		else l = mid;
	}
	
	vector<pair<int,int>> impt = getall(l);
	sort(impt.begin(),impt.end(),cmp);
	for (auto x : impt){
		printf("%lld\n",abs(origX[x.first]-origX[x.second])+abs(origY[x.first]-origY[x.second]));
	}
	for (int x = impt.size(); x<K; x++){
		printf("%lld\n",r);
	}
	
}

Compilation message (stderr)

road_construction.cpp: In function 'long long int check(long long int)':
road_construction.cpp:46:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   while (c<pts.size() && pts[c].first.first<=x.first.first+dist){
      |          ~^~~~~~~~~~~
road_construction.cpp: In function 'std::vector<std::pair<long long int, long long int> > getall(long long int)':
road_construction.cpp:61:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   while (c<pts.size() && pts[c].first.first<=x.first.first+dist){
      |          ~^~~~~~~~~~~
road_construction.cpp: At global scope:
road_construction.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main(){
      | ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |  scanf("%lld%lld",&n,&K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%lld%lld",&origX[x],&origY[x]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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