oj.uz

Submission #394012

# Submission time Handle Problem Language Result Execution time Memory
394012 2021-04-25T08:18:45 Z oolimry Road Construction (JOI21_road_construction) C++17
100 / 100
 2176 ms 15288 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define x first
#define y second
typedef long long lint;
typedef pair<lint, lint> ii;

int n, K;
vector<ii> points;
vector<lint> ans;
set<ii> S;

inline lint get(int a, int b){
	return max(abs(points[a].x - points[b].x), abs(points[a].y - points[b].y));
}
void solve(lint dis){
	ans.clear();
	S.clear();
	int ptr = 0;
	for(int i = 0;i < n;i++){
		ii p = points[i];
		
		while(true){
			if(p.x - points[ptr].x <= dis) break;
			else{
				S.erase(ii(points[ptr].y, ptr));
				ptr++;
			}
		}
		
		auto it = S.lower_bound({p.y - dis, -1});
		while(it != S.end()){
			if(it->first > p.y + dis) break;
			ans.push_back(get(it->second, i));
			if(sz(ans) >= K) return;
			it++;
		} 
		
		S.insert(ii(p.y, i));
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> K;
	for(int i = 1;i <= n;i++){
		lint x, y; cin >> x >> y;
		points.push_back(ii(x+y,x-y));
	}
	sort(all(points));
	
	lint low = 0; lint high = 4e9;
	while(low != high-1){
		lint mid = (low+high)/2;
		solve(mid);
		if(sz(ans) >= K) high = mid;
		else low = mid;
	}
	
	solve(low);
	sort(all(ans));
	while(sz(ans) < K) ans.push_back(high);
	for(lint x : ans) cout << x << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 5020 KB Output is correct
2 Correct 157 ms 5060 KB Output is correct
3 Correct 150 ms 5060 KB Output is correct
4 Correct 143 ms 5060 KB Output is correct
5 Correct 151 ms 3872 KB Output is correct
6 Correct 4 ms 332 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 12480 KB Output is correct
2 Correct 417 ms 12480 KB Output is correct
3 Correct 121 ms 4932 KB Output is correct
4 Correct 318 ms 12208 KB Output is correct
5 Correct 352 ms 12460 KB Output is correct
6 Correct 348 ms 12464 KB Output is correct
7 Correct 311 ms 11860 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 9392 KB Output is correct
2 Correct 342 ms 9380 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 152 ms 7240 KB Output is correct
5 Correct 391 ms 9648 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 9392 KB Output is correct
2 Correct 342 ms 9380 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 152 ms 7240 KB Output is correct
5 Correct 391 ms 9648 KB Output is correct
6 Correct 474 ms 9416 KB Output is correct
7 Correct 457 ms 9376 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 362 ms 9360 KB Output is correct
11 Correct 129 ms 7216 KB Output is correct
12 Correct 462 ms 9728 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 5020 KB Output is correct
2 Correct 157 ms 5060 KB Output is correct
3 Correct 150 ms 5060 KB Output is correct
4 Correct 143 ms 5060 KB Output is correct
5 Correct 151 ms 3872 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 1028 ms 7948 KB Output is correct
8 Correct 1035 ms 7968 KB Output is correct
9 Correct 144 ms 5136 KB Output is correct
10 Correct 558 ms 7424 KB Output is correct
11 Correct 338 ms 7292 KB Output is correct
12 Correct 415 ms 8016 KB Output is correct
13 Correct 493 ms 7012 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 5020 KB Output is correct
2 Correct 157 ms 5060 KB Output is correct
3 Correct 150 ms 5060 KB Output is correct
4 Correct 143 ms 5060 KB Output is correct
5 Correct 151 ms 3872 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 403 ms 12480 KB Output is correct
8 Correct 417 ms 12480 KB Output is correct
9 Correct 121 ms 4932 KB Output is correct
10 Correct 318 ms 12208 KB Output is correct
11 Correct 352 ms 12460 KB Output is correct
12 Correct 348 ms 12464 KB Output is correct
13 Correct 311 ms 11860 KB Output is correct
14 Correct 265 ms 9392 KB Output is correct
15 Correct 342 ms 9380 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 152 ms 7240 KB Output is correct
18 Correct 391 ms 9648 KB Output is correct
19 Correct 474 ms 9416 KB Output is correct
20 Correct 457 ms 9376 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 362 ms 9360 KB Output is correct
24 Correct 129 ms 7216 KB Output is correct
25 Correct 462 ms 9728 KB Output is correct
26 Correct 1028 ms 7948 KB Output is correct
27 Correct 1035 ms 7968 KB Output is correct
28 Correct 144 ms 5136 KB Output is correct
29 Correct 558 ms 7424 KB Output is correct
30 Correct 338 ms 7292 KB Output is correct
31 Correct 415 ms 8016 KB Output is correct
32 Correct 493 ms 7012 KB Output is correct
33 Correct 2163 ms 15248 KB Output is correct
34 Correct 2176 ms 15264 KB Output is correct
35 Correct 1386 ms 14484 KB Output is correct
36 Correct 683 ms 15288 KB Output is correct
37 Correct 670 ms 15252 KB Output is correct
38 Correct 764 ms 14000 KB Output is correct