Submission #1125971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125971		Kel_Mahmut	Road Construction (JOI21_road_construction)	C++20	5 / 100	10090 ms	32828 KiB

road_construction

#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

int main(){
	int n, k;
	cin >> n >> k;
	vector<pair<ll, ll>> v(n);
	for(int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;

	map<int, vector<int>> col;
	vector<int> X;
	for(int i = 0; i < n; i++) col[v[i].first].pb(v[i].second);
	
	for(auto &[ind, ar] : col){
		X.pb(ind);
		sort(all(ar));
	}


	// if(n <= 1000){
	// 	auto calc = [&](pair<ll, ll> a, pair<ll, ll> b){
	// 		return abs(a.first - b.first) + abs(a.second - b.second);
	// 	};

	// 	priority_queue<ll, vector<ll>, greater<ll>> pq;
	// 	for(int i = 0; i < n; i++){
	// 		for(int j = i + 1; j < n; j++){
	// 			pq.push(calc(v[i], v[j]));
	// 		}
	// 	}

	// 	for(int i = 0; i < k; i++){
	// 		cout << pq.top() << endl;
	// 		pq.pop();
	// 	}
	// 	exit(0);
	// }

	auto calc = [&](pair<ll, ll> a, pair<ll, ll> b){
		return abs(a.first - b.first) + abs(a.second - b.second);
	};

	sort(all(v));
	auto check = [&](ll l){
		int cnt = 0;
		for(int i = 0; i < n; i++){
			int indx = lower_bound(all(X), v[i].first) - X.begin();
			{
				int indy = lower_bound(all(col[X[indx]]), v[i].second) - col[X[indx]].begin();
				for(int j = indy + 1; j < (int) col[X[indx]].size(); j++){
					pair<ll, ll> cur = make_pair(X[indx], col[X[indx]][j]);
					if(calc(v[i], cur) <= l){
						cnt++;
					}
					else break;
				}
			}
			for(int j = indx + 1; j < (int) X.size(); j++){

				if(abs(v[i].first - X[j]) > l) break;
				int indy = lower_bound(all(col[X[j]]), v[i].second) - col[X[j]].begin();
				//yukari
				{
					for(int k = indy; k < (int) col[X[j]].size(); k++){
						pair<ll, ll> cur = make_pair(X[j], col[X[j]][k]);
						if(calc(v[i], cur) <= l){
							cnt++;
						}
						else break;
					}
				}
				//asagi
				{
					for(int k = indy - 1; k >= 0; k--){
						pair<ll, ll> cur = make_pair(X[j], col[X[j]][k]);
						if(calc(v[i], cur) <= l){
							cnt++;
						}
						else break;
					}
				}
			}
			if(cnt >= k) break;
		}

		return cnt >= k;
	};

	ll tl = 0, tr = 1e12;
	while(tr - tl > 1){
		ll tm = (tl + tr) / 2;
		if(check(tm))
			tr = tm;
		else 
			tl = tm;
	}

	priority_queue<ll, vector<ll>, greater<ll>> pq;
	for(int i = 0; i < n; i++){
		int indx = lower_bound(all(X), v[i].first) - X.begin();
		{
			int indy = lower_bound(all(col[X[indx]]), v[i].second) - col[X[indx]].begin();
			for(int j = indy + 1; j < (int) col[X[indx]].size(); j++){
				pair<ll, ll> cur = make_pair(X[indx], col[X[indx]][j]);
				if(calc(v[i], cur) <= tl){
					pq.push(calc(v[i], cur));
				}
				else break;
			}
		}
		for(int j = indx + 1; j < (int) X.size(); j++){

			int indy = lower_bound(all(col[X[j]]), v[i].second) - col[X[j]].begin();
			//yukari
			{
				for(int k = indy; k < (int) col[X[j]].size(); k++){
					pair<ll, ll> cur = make_pair(X[j], col[X[j]][k]);
					if(calc(v[i], cur) <= tl){
						pq.push(calc(v[i], cur));
					}
					else break;
				}
			}
			//asagi
			{
				for(int k = indy - 1; k >= 0; k--){
					pair<ll, ll> cur = make_pair(X[j], col[X[j]][k]);
					if(calc(v[i], cur) <= tl){
						pq.push(calc(v[i], cur));
					}
					else break;
				}
			}
		}
	}

	assert((int) pq.size() < k);

	while( (int) pq.size() < k){
		pq.push(tr);
	}

	for(int i = 0; i < k; i++){
		cout << pq.top() << endl;
		pq.pop();
	}
}

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