oj.uz

Submission #567995

# Submission time Handle Problem Language Result Execution time Memory
567995 2022-05-24T13:27:36 Z Arvin Road Construction (JOI21_road_construction) C++11
6 / 100
 696 ms 67508 KB 
#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[maxN], cY[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, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> 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<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<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});
		}
		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});
		}
	}
	
	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);
			
			int idxL = lower_bound(cX[r].begin(), cX[r].end(), p[idx].second-dif) - cX[r].begin();
			int idxR = lower_bound(cX[r].begin(), cX[r].end(), p[idx].second+dif+1) - cX[r].begin();
			
			for(int i=0;i<idxR-idxL;i++){
				cout << val << "\n";
				k--;
			}
			if(r+1 >= vX.size()) continue;
			
			dif = abs(vX[r+1] - p[idx].first);
			pq.push({dif, 0, idx, r+1});
		} else {
			ll dif = abs(vY[r] - p[idx].second);
			
			int idxL = lower_bound(cY[r].begin(), cY[r].end(), p[idx].first-dif+1) - cY[r].begin();
			int idxR = lower_bound(cY[r].begin(), cY[r].end(), p[idx].first+dif) - cY[r].begin();
			
			for(int i=0;i<idxR-idxL;i++){
				cout << val << "\n";
				k--;
			}

			if(r+1 >= vY.size()) continue;
			
			dif = abs(vY[r+1] - p[idx].second);
			pq.push({dif, 1, idx, r+1});
		}
	}
    return 0;
}

Compilation message

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()){
      |      ~~~~~~~~~~~~~~^~~~~~~~~~~
road_construction.cpp:80:11: 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]
   80 |    if(r+1 >= vX.size()) continue;
      |       ~~~~^~~~~~~~~~~~
road_construction.cpp:95:11: 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]
   95 |    if(r+1 >= vY.size()) continue;
      |       ~~~~^~~~~~~~~~~~
road_construction.cpp:67:81: warning: unused variable 'idx2' [-Wunused-variable]
   67 |   ll val = pq.top()[0], type = pq.top()[1], idx = pq.top()[2], r = pq.top()[3], idx2 = pq.top()[4];
      |                                                                                 ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 35932 KB Output is correct
2 Correct 164 ms 35860 KB Output is correct
3 Correct 124 ms 36020 KB Output is correct
4 Correct 131 ms 36060 KB Output is correct
5 Correct 142 ms 34920 KB Output is correct
6 Incorrect 39 ms 33320 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 61956 KB Output is correct
2 Correct 630 ms 61960 KB Output is correct
3 Correct 119 ms 35988 KB Output is correct
4 Correct 561 ms 61728 KB Output is correct
5 Correct 579 ms 61944 KB Output is correct
6 Correct 536 ms 61980 KB Output is correct
7 Correct 565 ms 61452 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 61464 KB Output is correct
2 Correct 696 ms 61460 KB Output is correct
3 Correct 43 ms 33080 KB Output is correct
4 Correct 351 ms 61440 KB Output is correct
5 Incorrect 201 ms 67508 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 61464 KB Output is correct
2 Correct 696 ms 61460 KB Output is correct
3 Correct 43 ms 33080 KB Output is correct
4 Correct 351 ms 61440 KB Output is correct
5 Incorrect 201 ms 67508 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 35932 KB Output is correct
2 Correct 164 ms 35860 KB Output is correct
3 Correct 124 ms 36020 KB Output is correct
4 Correct 131 ms 36060 KB Output is correct
5 Correct 142 ms 34920 KB Output is correct
6 Incorrect 39 ms 33320 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 35932 KB Output is correct
2 Correct 164 ms 35860 KB Output is correct
3 Correct 124 ms 36020 KB Output is correct
4 Correct 131 ms 36060 KB Output is correct
5 Correct 142 ms 34920 KB Output is correct
6 Incorrect 39 ms 33320 KB Output isn't correct
7 Halted 0 ms 0 KB -