Submission #544391

#	Time	Username	Problem	Language	Result	Execution time	Memory
544391		ivan_tudor	Road Construction (JOI21_road_construction)	C++14	100 / 100	7670 ms	58236 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;


const int N = 250005;
struct points{
	long long x, y;
	int id;
	bool operator < (points oth) const{
		if(y == oth.y)
			return x < oth.x;
		return y < oth.y;
	}
};

using ordered_set = tree<points, null_type,less<points>, rb_tree_tag,tree_order_statistics_node_update>;

int n;
points v[N];
points vinit[N];
vector<long long> dist;
long long getdst(int i, int j){
	return llabs(vinit[i].x - vinit[j].x) + llabs(vinit[i].y - vinit[j].y);
}
bool cmp(pair<points, bool> a, pair<points, bool> b){
	if(a.first.x == b.first.x){
		return a.second < b.second;
	}
	return a.first.x < b.first.x;
}
long long check(long long dst, bool ok){
  vector<pair<points, bool>> vc;
  for(int i = 1; i <=n; i++){
		vc.push_back({v[i], true});
		vc.push_back({{v[i].x + dst + 1, v[i].y, v[i].id}, false});
  }
  sort(vc.begin(), vc.end(), cmp);
	ordered_set oset;
	long long ans = 0;
	for(auto ev:vc){
		if(ev.second == false){
			ev.first.x -= (dst + 1);
			oset.erase(ev.first);
		}
		else{
			points cur = ev.first;
			if(ok == true){
				auto itrfirst = oset.lower_bound({LLONG_MIN, cur.y - dst});
				auto itrlast = oset.upper_bound({LLONG_MAX, cur.y + dst}); /// e pe urm buna
				while(itrfirst != itrlast){
					points aux = (*itrfirst);
					dist.push_back(getdst(aux.id, cur.id));
					itrfirst++;
				}
			}
			else{
				long long curr = 0;
        curr -= oset.order_of_key({LLONG_MIN, cur.y - dst});
        curr += oset.order_of_key({LLONG_MIN, cur.y + dst + 1});

        ans += curr;
			}
			oset.insert(cur);
		}
  }
  return ans;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int k;
  cin>>n>>k;
  for(int i = 1; i<=n; i++){
		int x, y;
		cin>>x>>y;
		vinit[i].x = x;
		vinit[i].y = y;

		v[i].x = x + y;
		v[i].y = x - y;
		v[i].id = i;
  }
	long long dst = 0;
	for(long long p2 = (1LL <<(32)); p2; p2>>=1){
		long long cnt = check(dst + p2, false);
		if(cnt < k){
			dst += p2;
		}
	}
	check(dst, true);
	while(dist.size() < k){
		dist.push_back(dst + 1);
	}
	sort(dist.begin(), dist.end());
	for(auto x:dist){
		cout<<x<<"\n";
	}
	return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:96:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |  while(dist.size() < k){
      |        ~~~~~~~~~~~~^~~

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