oj.uz

Submission #755765

# Submission time Handle Problem Language Result Execution time Memory
755765 2023-06-10T15:58:05 Z Dan4Life Road Construction (JOI21_road_construction) C++17
12 / 100
 890 ms 9640 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!=end(S) and sz(ans)<K and itr1->first < v[i][1]+d)
			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";
}

Compilation message

road_construction.cpp: In function 'bool chk(long long int)':
road_construction.cpp:19:8: warning: variable 'itr2' set but not used [-Wunused-but-set-variable]
   19 |   auto itr2 = S.lower_bound({v[i][1]+d+1,-1});
      |        ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 5000 KB Output is correct
2 Correct 117 ms 5040 KB Output is correct
3 Correct 116 ms 5012 KB Output is correct
4 Correct 104 ms 5144 KB Output is correct
5 Correct 110 ms 3876 KB Output is correct
6 Correct 3 ms 340 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 364 ms 9464 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 227 ms 4548 KB Output is correct
2 Correct 296 ms 4508 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 124 ms 4548 KB Output is correct
5 Correct 337 ms 4488 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 4548 KB Output is correct
2 Correct 296 ms 4508 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 124 ms 4548 KB Output is correct
5 Correct 337 ms 4488 KB Output is correct
6 Correct 448 ms 4508 KB Output is correct
7 Correct 399 ms 9400 KB Output is correct
8 Correct 1 ms 280 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 321 ms 9404 KB Output is correct
11 Correct 96 ms 7288 KB Output is correct
12 Incorrect 348 ms 9640 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 5000 KB Output is correct
2 Correct 117 ms 5040 KB Output is correct
3 Correct 116 ms 5012 KB Output is correct
4 Correct 104 ms 5144 KB Output is correct
5 Correct 110 ms 3876 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 881 ms 7964 KB Output is correct
8 Correct 890 ms 7972 KB Output is correct
9 Correct 108 ms 5140 KB Output is correct
10 Incorrect 472 ms 7424 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 5000 KB Output is correct
2 Correct 117 ms 5040 KB Output is correct
3 Correct 116 ms 5012 KB Output is correct
4 Correct 104 ms 5144 KB Output is correct
5 Correct 110 ms 3876 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Incorrect 364 ms 9464 KB Output isn't correct
8 Halted 0 ms 0 KB -