oj.uz

Submission #755769

# Submission time Handle Problem Language Result Execution time Memory
755769 2023-06-10T15:59:42 Z Dan4Life Road Construction (JOI21_road_construction) C++17
12 / 100
 1027 ms 9488 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); 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 114 ms 4940 KB Output is correct
2 Correct 111 ms 4996 KB Output is correct
3 Correct 108 ms 5068 KB Output is correct
4 Correct 99 ms 5128 KB Output is correct
5 Correct 110 ms 3788 KB Output is correct
6 Correct 4 ms 340 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 358 ms 9488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 4556 KB Output is correct
2 Correct 304 ms 4444 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 124 ms 4520 KB Output is correct
5 Correct 351 ms 4528 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 4556 KB Output is correct
2 Correct 304 ms 4444 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 124 ms 4520 KB Output is correct
5 Correct 351 ms 4528 KB Output is correct
6 Correct 472 ms 4548 KB Output is correct
7 Correct 408 ms 4556 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 318 ms 4564 KB Output is correct
11 Correct 112 ms 4568 KB Output is correct
12 Incorrect 393 ms 4528 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 4940 KB Output is correct
2 Correct 111 ms 4996 KB Output is correct
3 Correct 108 ms 5068 KB Output is correct
4 Correct 99 ms 5128 KB Output is correct
5 Correct 110 ms 3788 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 982 ms 5960 KB Output is correct
8 Correct 1027 ms 6016 KB Output is correct
9 Correct 107 ms 5120 KB Output is correct
10 Incorrect 517 ms 5380 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 4940 KB Output is correct
2 Correct 111 ms 4996 KB Output is correct
3 Correct 108 ms 5068 KB Output is correct
4 Correct 99 ms 5128 KB Output is correct
5 Correct 110 ms 3788 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Incorrect 358 ms 9488 KB Output isn't correct
8 Halted 0 ms 0 KB -