oj.uz

Submission #567918

# Submission time Handle Problem Language Result Execution time Memory
567918 2022-05-24T11:03:15 Z Arvin Road Construction (JOI21_road_construction) C++11
11 / 100
 10000 ms 29072 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});
	}
	
	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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 2972 KB Output is correct
2 Correct 116 ms 3036 KB Output is correct
3 Correct 81 ms 3140 KB Output is correct
4 Correct 84 ms 3132 KB Output is correct
5 Correct 98 ms 1832 KB Output is correct
6 Correct 6 ms 468 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 29072 KB Output is correct
2 Correct 411 ms 28996 KB Output is correct
3 Correct 99 ms 2892 KB Output is correct
4 Correct 229 ms 28828 KB Output is correct
5 Correct 252 ms 29008 KB Output is correct
6 Correct 274 ms 29040 KB Output is correct
7 Correct 263 ms 28624 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 28524 KB Output is correct
2 Correct 401 ms 28544 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 117 ms 28524 KB Output is correct
5 Execution timed out 10027 ms 28624 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 28524 KB Output is correct
2 Correct 401 ms 28544 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 117 ms 28524 KB Output is correct
5 Execution timed out 10027 ms 28624 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 2972 KB Output is correct
2 Correct 116 ms 3036 KB Output is correct
3 Correct 81 ms 3140 KB Output is correct
4 Correct 84 ms 3132 KB Output is correct
5 Correct 98 ms 1832 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Execution timed out 10095 ms 13292 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 2972 KB Output is correct
2 Correct 116 ms 3036 KB Output is correct
3 Correct 81 ms 3140 KB Output is correct
4 Correct 84 ms 3132 KB Output is correct
5 Correct 98 ms 1832 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 390 ms 29072 KB Output is correct
8 Correct 411 ms 28996 KB Output is correct
9 Correct 99 ms 2892 KB Output is correct
10 Correct 229 ms 28828 KB Output is correct
11 Correct 252 ms 29008 KB Output is correct
12 Correct 274 ms 29040 KB Output is correct
13 Correct 263 ms 28624 KB Output is correct
14 Correct 307 ms 28524 KB Output is correct
15 Correct 401 ms 28544 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 117 ms 28524 KB Output is correct
18 Execution timed out 10027 ms 28624 KB Time limit exceeded
19 Halted 0 ms 0 KB -