oj.uz

Submission #567969

# Submission time Handle Problem Language Result Execution time Memory
567969 2022-05-24T12:39:04 Z Arvin Road Construction (JOI21_road_construction) C++11
38 / 100
 10000 ms 72720 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, 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<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, 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 >= vX.size()) 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 >= vY.size()) 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

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:77:12: 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]
   77 |     if(r+1 >= vX.size()) continue;
      |        ~~~~^~~~~~~~~~~~
road_construction.cpp:90:12: 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]
   90 |     if(r+1 >= vY.size()) continue;
      |        ~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 35964 KB Output is correct
2 Correct 199 ms 35908 KB Output is correct
3 Correct 153 ms 36072 KB Output is correct
4 Correct 154 ms 35948 KB Output is correct
5 Correct 210 ms 34796 KB Output is correct
6 Correct 42 ms 33344 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 67012 KB Output is correct
2 Correct 848 ms 67052 KB Output is correct
3 Correct 156 ms 35888 KB Output is correct
4 Correct 724 ms 66788 KB Output is correct
5 Correct 761 ms 66996 KB Output is correct
6 Correct 762 ms 66976 KB Output is correct
7 Correct 779 ms 66680 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 66668 KB Output is correct
2 Correct 875 ms 66688 KB Output is correct
3 Correct 39 ms 33192 KB Output is correct
4 Correct 464 ms 66676 KB Output is correct
5 Correct 269 ms 72720 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 66668 KB Output is correct
2 Correct 875 ms 66688 KB Output is correct
3 Correct 39 ms 33192 KB Output is correct
4 Correct 464 ms 66676 KB Output is correct
5 Correct 269 ms 72720 KB Output is correct
6 Correct 1267 ms 66732 KB Output is correct
7 Correct 1211 ms 66692 KB Output is correct
8 Correct 53 ms 33100 KB Output is correct
9 Correct 41 ms 33100 KB Output is correct
10 Correct 694 ms 68276 KB Output is correct
11 Correct 441 ms 66704 KB Output is correct
12 Correct 283 ms 72668 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 35964 KB Output is correct
2 Correct 199 ms 35908 KB Output is correct
3 Correct 153 ms 36072 KB Output is correct
4 Correct 154 ms 35948 KB Output is correct
5 Correct 210 ms 34796 KB Output is correct
6 Correct 42 ms 33344 KB Output is correct
7 Execution timed out 10064 ms 48764 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 35964 KB Output is correct
2 Correct 199 ms 35908 KB Output is correct
3 Correct 153 ms 36072 KB Output is correct
4 Correct 154 ms 35948 KB Output is correct
5 Correct 210 ms 34796 KB Output is correct
6 Correct 42 ms 33344 KB Output is correct
7 Correct 826 ms 67012 KB Output is correct
8 Correct 848 ms 67052 KB Output is correct
9 Correct 156 ms 35888 KB Output is correct
10 Correct 724 ms 66788 KB Output is correct
11 Correct 761 ms 66996 KB Output is correct
12 Correct 762 ms 66976 KB Output is correct
13 Correct 779 ms 66680 KB Output is correct
14 Correct 721 ms 66668 KB Output is correct
15 Correct 875 ms 66688 KB Output is correct
16 Correct 39 ms 33192 KB Output is correct
17 Correct 464 ms 66676 KB Output is correct
18 Correct 269 ms 72720 KB Output is correct
19 Correct 1267 ms 66732 KB Output is correct
20 Correct 1211 ms 66692 KB Output is correct
21 Correct 53 ms 33100 KB Output is correct
22 Correct 41 ms 33100 KB Output is correct
23 Correct 694 ms 68276 KB Output is correct
24 Correct 441 ms 66704 KB Output is correct
25 Correct 283 ms 72668 KB Output is correct
26 Execution timed out 10064 ms 48764 KB Time limit exceeded
27 Halted 0 ms 0 KB -