oj.uz

Submission #1104554

# Submission time Handle Problem Language Result Execution time Memory
1104554 2024-10-24T03:26:59 Z penguinhacker Road Construction (JOI21_road_construction) C++17
100 / 100
 1623 ms 13768 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=250000;
int n, k;
ar<ll, 2> a[mxN];
vector<ll> ans;

bool ok(ll x) {
	ans.clear();
	set<ar<ll, 2>> s;
	for (int i=0, j=0; ans.size()<k&&i<n; ++i) {
		for (; a[i][0]-a[j][0]>x; ++j)
			s.erase({a[j][1], a[j][0]});
		for (auto it=s.lower_bound({a[i][1]-x, (ll)-1e10}); ans.size()<k&&it!=s.end()&&(*it)[0]<=a[i][1]+x; ++it)
			ans.push_back(max(a[i][0]-(*it)[1], abs(a[i][1]-(*it)[0])));
		s.insert({a[i][1], a[i][0]});
	}
	return ans.size()<k;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i=0; i<n; ++i) {
		ll x, y;
		cin >> x >> y;
		a[i]={x+y, x-y};
	}
	sort(a, a+n);
	ll lb=0, rb=4e9;
	while(lb<rb) {
		ll mid=(lb+rb+1)/2; // look for max number so <k roads with that many
		if (ok(mid))
			lb=mid;
		else
			rb=mid-1;
	}
	ok(lb);
	sort(ans.begin(), ans.end());
	for (ll i : ans)
		cout << i << "\n";
	for (int i=0; i<k-ans.size(); ++i)
		cout << lb+1 << "\n";
	return 0;
}

Compilation message

road_construction.cpp: In function 'bool ok(long long int)':
road_construction.cpp:15:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |  for (int i=0, j=0; ans.size()<k&&i<n; ++i) {
      |                     ~~~~~~~~~~^~
road_construction.cpp:18:65: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |   for (auto it=s.lower_bound({a[i][1]-x, (ll)-1e10}); ans.size()<k&&it!=s.end()&&(*it)[0]<=a[i][1]+x; ++it)
      |                                                       ~~~~~~~~~~^~
road_construction.cpp:22:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |  return ans.size()<k;
      |         ~~~~~~~~~~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i=0; i<k-ans.size(); ++i)
      |                ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 5060 KB Output is correct
2 Correct 93 ms 5260 KB Output is correct
3 Correct 82 ms 5320 KB Output is correct
4 Correct 83 ms 5244 KB Output is correct
5 Correct 80 ms 4052 KB Output is correct
6 Correct 4 ms 336 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 10680 KB Output is correct
2 Correct 279 ms 10604 KB Output is correct
3 Correct 76 ms 5064 KB Output is correct
4 Correct 225 ms 10444 KB Output is correct
5 Correct 217 ms 10696 KB Output is correct
6 Correct 209 ms 10708 KB Output is correct
7 Correct 195 ms 10528 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 9328 KB Output is correct
2 Correct 258 ms 9444 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 116 ms 7248 KB Output is correct
5 Correct 335 ms 9732 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 9328 KB Output is correct
2 Correct 258 ms 9444 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 116 ms 7248 KB Output is correct
5 Correct 335 ms 9732 KB Output is correct
6 Correct 314 ms 9448 KB Output is correct
7 Correct 316 ms 9196 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 252 ms 9200 KB Output is correct
11 Correct 103 ms 7240 KB Output is correct
12 Correct 359 ms 9712 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 5060 KB Output is correct
2 Correct 93 ms 5260 KB Output is correct
3 Correct 82 ms 5320 KB Output is correct
4 Correct 83 ms 5244 KB Output is correct
5 Correct 80 ms 4052 KB Output is correct
6 Correct 4 ms 336 KB Output is correct
7 Correct 783 ms 8700 KB Output is correct
8 Correct 752 ms 8908 KB Output is correct
9 Correct 77 ms 5320 KB Output is correct
10 Correct 385 ms 8188 KB Output is correct
11 Correct 224 ms 7924 KB Output is correct
12 Correct 290 ms 8736 KB Output is correct
13 Correct 329 ms 7884 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 5060 KB Output is correct
2 Correct 93 ms 5260 KB Output is correct
3 Correct 82 ms 5320 KB Output is correct
4 Correct 83 ms 5244 KB Output is correct
5 Correct 80 ms 4052 KB Output is correct
6 Correct 4 ms 336 KB Output is correct
7 Correct 297 ms 10680 KB Output is correct
8 Correct 279 ms 10604 KB Output is correct
9 Correct 76 ms 5064 KB Output is correct
10 Correct 225 ms 10444 KB Output is correct
11 Correct 217 ms 10696 KB Output is correct
12 Correct 209 ms 10708 KB Output is correct
13 Correct 195 ms 10528 KB Output is correct
14 Correct 187 ms 9328 KB Output is correct
15 Correct 258 ms 9444 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 116 ms 7248 KB Output is correct
18 Correct 335 ms 9732 KB Output is correct
19 Correct 314 ms 9448 KB Output is correct
20 Correct 316 ms 9196 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 252 ms 9200 KB Output is correct
24 Correct 103 ms 7240 KB Output is correct
25 Correct 359 ms 9712 KB Output is correct
26 Correct 783 ms 8700 KB Output is correct
27 Correct 752 ms 8908 KB Output is correct
28 Correct 77 ms 5320 KB Output is correct
29 Correct 385 ms 8188 KB Output is correct
30 Correct 224 ms 7924 KB Output is correct
31 Correct 290 ms 8736 KB Output is correct
32 Correct 329 ms 7884 KB Output is correct
33 Correct 1623 ms 13444 KB Output is correct
34 Correct 1591 ms 13440 KB Output is correct
35 Correct 968 ms 12676 KB Output is correct
36 Correct 466 ms 13768 KB Output is correct
37 Correct 456 ms 13708 KB Output is correct
38 Correct 471 ms 12900 KB Output is correct