Submission #567962

#	Time	Username	Problem	Language	Result	Execution time	Memory
567962		Arvin	Road Construction (JOI21_road_construction)	C++11	38 / 100	10055 ms	105628 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll maxA = 1e13;
const int maxN = 3e5;

pair<ll, ll> p[maxN], q[maxN];
vector<ll> cX[2*maxN], cY[2*maxN];

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//	freopen("input.txt","r",stdin);
	
	int n, k;
	cin >> n >> k;
	
	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<ll> vX, vY;
	priority_queue<array<ll, 5>, vector<array<ll, 5>>, greater<array<ll, 5>>> pq;
	for(int x=0;x<n;x++){
		vX.push_back(p[x].first);
		vY.push_back(p[x].second);
	}
	
	sort(vX.begin(), vX.end());
	sort(vY.begin(), vY.end());
	vX.erase(unique(vX.begin(), vX.end()), vX.end());
	vY.erase(unique(vY.begin(), vY.end()), vY.end());
	
	for(int x=0;x<2*maxN;x++){
		cX[x].push_back(3*maxA);
		cY[x].push_back(3*maxA);
	}
	for(int x=0;x<n;x++){
		q[x] = {lower_bound(vX.begin(), vX.end(), p[x].first) - vX.begin(), lower_bound(vY.begin(), vY.end(), p[x].second) - vY.begin()};
		cX[q[x].first].push_back(p[x].second);
		cY[q[x].second].push_back(p[x].first);
	}
	for(int x=0;x<2*maxN;x++){
		sort(cX[x].begin(), cX[x].end());
		sort(cY[x].begin(), cY[x].end());
	}
	
	for(int x=0;x<n;x++){	
		if(q[x].first+1 < vX.size()){
			ll dif = abs(vX[q[x].first+1] - p[x].first);
			int idx = lower_bound(cX[q[x].first+1].begin(), cX[q[x].first+1].end(), p[x].second-dif) - cX[q[x].first+1].begin();
			pq.push({dif, 0, x, q[x].first+1, idx});
		}
		if(q[x].second+1 < vY.size()){
			ll dif = abs(vY[q[x].second+1] - p[x].second);
			int idx = lower_bound(cY[q[x].second+1].begin(), cY[q[x].second+1].end(), p[x].first-dif+1) - cY[q[x].second+1].begin();
			pq.push({dif, 1, x, q[x].second+1, idx});
		}
	}
	
	while(k > 0 && !pq.empty()){
		ll val = pq.top()[0], type = pq.top()[1], idx = pq.top()[2], r = pq.top()[3], idx2 = pq.top()[4];
		pq.pop();
		
		if(type == 0){
			ll dif = abs(vX[r] - p[idx].first);
			if(abs(cX[r][idx2] - p[idx].second) <= dif){
				cout << val << "\n";
				pq.push({val, 0, idx, r, idx2+1});
				k--;
			} else {
				if(r+1 >= 2*maxN) continue;
				
				ll dif = abs(vX[r+1] - p[idx].first);
				int idx2 = lower_bound(cX[r+1].begin(), cX[r+1].end(), p[idx].second-dif) - cX[r+1].begin();
				pq.push({dif, 0, idx, r+1, idx2});
			}
		} else {
			ll dif = abs(vY[r] - p[idx].second);
			if(abs(cY[r][idx2] - p[idx].first) < dif){
				cout << val << "\n";
				pq.push({val, 1, idx, r, idx2+1});
				k--;
			} else {
				if(r+1 >= 2*maxN) continue;
				
				ll dif = abs(vY[r+1] - p[idx].second);
				int idx2 = lower_bound(cY[r+1].begin(), cY[r+1].end(), p[idx].first-dif+1) - cY[r+1].begin();
				pq.push({dif, 1, idx, r+1, idx2});
			}
		}
	}
    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:54:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   if(q[x].first+1 < vX.size()){
      |      ~~~~~~~~~~~~~^~~~~~~~~~~
road_construction.cpp:59:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if(q[x].second+1 < vY.size()){
      |      ~~~~~~~~~~~~~~^~~~~~~~~~~

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