제출 #567916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
567916		Arvin	Road Construction (JOI21_road_construction)	C++11	11 / 100	10080 ms	29100 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll maxA = 1e10;

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

	int n, k;
	cin >> n >> k;
	
	pair<ll, ll> p[n];
	for(int x=0;x<n;x++){
		cin >> p[x].first >> p[x].second;
		p[x] = {p[x].first+p[x].second+maxA, p[x].first-p[x].second+maxA};
	}
	
	vector<pair<ll, ll>> vX, vY;
	priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;
	for(int x=0;x<n;x++){
		vX.push_back({p[x].first, x});
		vY.push_back({p[x].second, x});
	}
	
	sort(vX.begin(), vX.end());
	sort(vY.begin(), vY.end());
	
	for(int x=0;x+1<n;x++){
		pq.push({vX[x+1].first-vX[x].first, 0, x, x+1});
		pq.push({vY[x+1].first-vY[x].first, 1, x, x+1});
	}
	
	while(k > 0 && !pq.empty()){
		ll val = pq.top()[0], type = pq.top()[1], l = pq.top()[2], r = pq.top()[3];
		pq.pop();
		
		if(type == 0){
			int idx1 = vX[l].second, idx2 = vX[r].second;
			if(max(abs(p[idx2].first-p[idx1].first), abs(p[idx2].second-p[idx1].second)) == val){
				cout << val << "\n";
				k--;
			}
			if(r+1 < n){
				pq.push({p[vX[r+1].second].first-p[vX[l].second].first, 0, l, r+1});
			}
		} else {
			int idx1 = vY[l].second, idx2 = vY[r].second;
			if(abs(p[idx2].first-p[idx1].first) < abs(p[idx2].second-p[idx1].second) && abs(p[idx2].second-p[idx1].second) == val){
				cout << val << "\n";
				k--;
			}
			if(r+1 < n){
				pq.push({p[vY[r+1].second].second-p[vY[l].second].second, 1, l, r+1});
			}
		}
	}
    return 0;
}

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