oj.uz

Submission #755771

# Submission time Handle Problem Language Result Execution time Memory
755771 2023-06-10T16:00:03 Z Dan4Life Road Construction (JOI21_road_construction) C++17
100 / 100
 2219 ms 15320 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)2.5e5+10;
int n, K;
vector<int> ans;
vector<array<int,2>> v;

int calc(int i, int j){ return max(abs(v[i][0]-v[j][0]),abs(v[i][1]-v[j][1])); }

bool chk(int d){
	set<pair<int,int>> S; S.clear(); ans.clear();
	for(int i=0, j=0; i < n and sz(ans)<K; i++){
		while(v[i][0]-v[j][0]>d) S.erase({v[j][1],j}), j++;
		auto itr1 = S.lower_bound({v[i][1]-d,-1});
		auto itr2 = S.lower_bound({v[i][1]+d+1,-1});
		while(itr1!=itr2 and sz(ans)<K)
			ans.pb(calc(itr1->second,i)), itr1++;
		S.insert({v[i][1],i});
	}
	return sz(ans)>=K;
}

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> K; int x, y;
	for(int i = 0; i < n; i++)
		cin >> x >> y, v.pb({x+y,x-y});
	sort(all(v));
	int l = 0, r = (int)4e9;
	while(l<r){
		int mid = (l+r)>>1;
		if(chk(mid)) r=mid;
		else l=mid+1;
	}
	chk(l-1); sort(all(ans)); while(sz(ans)<K) ans.pb(l);
	for(auto u : ans) cout << u << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 5000 KB Output is correct
2 Correct 123 ms 5000 KB Output is correct
3 Correct 109 ms 5108 KB Output is correct
4 Correct 107 ms 5128 KB Output is correct
5 Correct 107 ms 3788 KB Output is correct
6 Correct 4 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 9476 KB Output is correct
2 Correct 365 ms 9396 KB Output is correct
3 Correct 111 ms 4880 KB Output is correct
4 Correct 262 ms 9228 KB Output is correct
5 Correct 306 ms 9396 KB Output is correct
6 Correct 277 ms 9476 KB Output is correct
7 Correct 296 ms 8688 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 4520 KB Output is correct
2 Correct 341 ms 4460 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 134 ms 4528 KB Output is correct
5 Correct 377 ms 4552 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 4520 KB Output is correct
2 Correct 341 ms 4460 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 134 ms 4528 KB Output is correct
5 Correct 377 ms 4552 KB Output is correct
6 Correct 525 ms 4460 KB Output is correct
7 Correct 417 ms 4448 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 317 ms 4512 KB Output is correct
11 Correct 110 ms 4556 KB Output is correct
12 Correct 384 ms 4476 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 5000 KB Output is correct
2 Correct 123 ms 5000 KB Output is correct
3 Correct 109 ms 5108 KB Output is correct
4 Correct 107 ms 5128 KB Output is correct
5 Correct 107 ms 3788 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 1016 ms 5928 KB Output is correct
8 Correct 1044 ms 5920 KB Output is correct
9 Correct 110 ms 5196 KB Output is correct
10 Correct 516 ms 5292 KB Output is correct
11 Correct 312 ms 5256 KB Output is correct
12 Correct 408 ms 7960 KB Output is correct
13 Correct 476 ms 6980 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 5000 KB Output is correct
2 Correct 123 ms 5000 KB Output is correct
3 Correct 109 ms 5108 KB Output is correct
4 Correct 107 ms 5128 KB Output is correct
5 Correct 107 ms 3788 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 389 ms 9476 KB Output is correct
8 Correct 365 ms 9396 KB Output is correct
9 Correct 111 ms 4880 KB Output is correct
10 Correct 262 ms 9228 KB Output is correct
11 Correct 306 ms 9396 KB Output is correct
12 Correct 277 ms 9476 KB Output is correct
13 Correct 296 ms 8688 KB Output is correct
14 Correct 260 ms 4520 KB Output is correct
15 Correct 341 ms 4460 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 134 ms 4528 KB Output is correct
18 Correct 377 ms 4552 KB Output is correct
19 Correct 525 ms 4460 KB Output is correct
20 Correct 417 ms 4448 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 317 ms 4512 KB Output is correct
24 Correct 110 ms 4556 KB Output is correct
25 Correct 384 ms 4476 KB Output is correct
26 Correct 1016 ms 5928 KB Output is correct
27 Correct 1044 ms 5920 KB Output is correct
28 Correct 110 ms 5196 KB Output is correct
29 Correct 516 ms 5292 KB Output is correct
30 Correct 312 ms 5256 KB Output is correct
31 Correct 408 ms 7960 KB Output is correct
32 Correct 476 ms 6980 KB Output is correct
33 Correct 2219 ms 15296 KB Output is correct
34 Correct 2197 ms 15216 KB Output is correct
35 Correct 1319 ms 14508 KB Output is correct
36 Correct 667 ms 15292 KB Output is correct
37 Correct 684 ms 15320 KB Output is correct
38 Correct 744 ms 14008 KB Output is correct