oj.uz

Submission #567915

# Submission time Handle Problem Language Result Execution time Memory
567915 2022-05-24T10:59:03 Z Arvin Road Construction (JOI21_road_construction) C++11
11 / 100
 10000 ms 32936 KB 
#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});
	}
	
	vector<ll> ans;
	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){
				ans.push_back(val);
				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){
				ans.push_back(val);
				k--;
			}
			if(r+1 < n){
				pq.push({p[vY[r+1].second].second-p[vY[l].second].second, 1, l, r+1});
			}
		}
	}
	
	for(auto val : ans){
		cout << val << "\n";
	}
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 4984 KB Output is correct
2 Correct 114 ms 5088 KB Output is correct
3 Correct 84 ms 5088 KB Output is correct
4 Correct 82 ms 5192 KB Output is correct
5 Correct 104 ms 4024 KB Output is correct
6 Correct 7 ms 468 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 32836 KB Output is correct
2 Correct 400 ms 32888 KB Output is correct
3 Correct 79 ms 4932 KB Output is correct
4 Correct 232 ms 32668 KB Output is correct
5 Correct 262 ms 32936 KB Output is correct
6 Correct 245 ms 32916 KB Output is correct
7 Correct 267 ms 32208 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 28528 KB Output is correct
2 Correct 371 ms 28524 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 116 ms 28532 KB Output is correct
5 Execution timed out 10052 ms 28524 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 28528 KB Output is correct
2 Correct 371 ms 28524 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 116 ms 28532 KB Output is correct
5 Execution timed out 10052 ms 28524 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 4984 KB Output is correct
2 Correct 114 ms 5088 KB Output is correct
3 Correct 84 ms 5088 KB Output is correct
4 Correct 82 ms 5192 KB Output is correct
5 Correct 104 ms 4024 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Execution timed out 10009 ms 13296 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 4984 KB Output is correct
2 Correct 114 ms 5088 KB Output is correct
3 Correct 84 ms 5088 KB Output is correct
4 Correct 82 ms 5192 KB Output is correct
5 Correct 104 ms 4024 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 405 ms 32836 KB Output is correct
8 Correct 400 ms 32888 KB Output is correct
9 Correct 79 ms 4932 KB Output is correct
10 Correct 232 ms 32668 KB Output is correct
11 Correct 262 ms 32936 KB Output is correct
12 Correct 245 ms 32916 KB Output is correct
13 Correct 267 ms 32208 KB Output is correct
14 Correct 286 ms 28528 KB Output is correct
15 Correct 371 ms 28524 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 116 ms 28532 KB Output is correct
18 Execution timed out 10052 ms 28524 KB Time limit exceeded
19 Halted 0 ms 0 KB -