oj.uz

Submission #943331

# Submission time Handle Problem Language Result Execution time Memory
943331 2024-03-11T10:57:03 Z shoryu386 Road Construction (JOI21_road_construction) C++17
100 / 100
 6557 ms 41436 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define int long long

template <typename T>
using pbds_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define N 250007
int fw[N];
void update(int x, int v){
	x++;
	for (; x < N; x+= x&(-x)) fw[x] += v;
}
int sum(int x) {
    x++;
    int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}
inline int range_sum(int x, int y) { //inclusive
    return sum(y)-sum(x-1);
}


main(){
	int n, k; cin >> n >> k;
	
	pair<int, int> arr[n];
	for (int x = 0; x < n; x++){
		cin >> arr[x].first >> arr[x].second;
	}
	
	//consider manhattan distance trick?
	for (int x = 0; x < n; x++){
		arr[x] = {arr[x].first + arr[x].second, arr[x].first - arr[x].second};
	}
	sort(arr, arr+n); //sorted by x-coord
	
	//now chebyshev distance, dist = max of difference
	
	//I want to bsearch, but bsearch only gives location of boundary; I need sum of boundary
	
	set<int> pts;
	for (int x = 0; x < n; x++){
		pts.insert(arr[x].second);
	}
	
	unordered_map<int, int> disc;
	vector<int> discPts;
	
	int ptr = 0;
	for (auto pt : pts){
		disc[pt] = ptr; ptr++;
		
		discPts.push_back(pt);
	}
	
	int l = 0, r = 4'000'000'000LL, ans = 4'000'000'000LL;
	while (l <= r){
		int m = (l+r)/2;
		int cnt = 0;
		
		memset(fw, 0, sizeof(fw));
		deque<pair<int, int>> pq;
		for (int x = 0; x < n; x++){
			while (!pq.empty() && pq.front().first <= arr[x].first){
				update(disc[arr[ pq.front().second ].second], -1);
				pq.pop_front();
			}
			
			//we want sum <= arr[x].second-m-1
			//we want sum <= arr[x].second+m
			
			int high = 0;
			auto upper = lower_bound(discPts.begin(), discPts.end(), arr[x].second+m+1);
			if (upper != discPts.begin()){
				high = disc[ *prev(upper) ];
			}
			
			int low = 0;
			auto lower = lower_bound(discPts.begin(), discPts.end(), arr[x].second-m);
			if (lower != discPts.begin()){
				low = disc[ *prev(lower) ];
			}
			
			cnt += sum(high) - sum(low);
			
			update(disc[arr[x].second], 1);
			pq.push_back({arr[x].first+m+1, x});
		}
		
		if (cnt < k){
			l = m+1;
		}
		else{
			ans = m;
			r = m-1;
		}
	}
	
	
	vector<int> clown;
	
	int ptrr = 0;
	multiset<pair<int, int>> ypts;
	for (int x = 0; x < n; x++){
		
		while (ptrr != n && arr[ptrr].first - arr[x].first <= ans){
			ypts.insert({arr[ptrr].second, arr[ptrr].first});
			ptrr++;
		}
		
		ypts.erase({arr[x].second, arr[x].first});
		for (auto y = ypts.lower_bound({arr[x].second - ans, LLONG_MIN}); y != ypts.lower_bound({arr[x].second + ans+1, LLONG_MIN}); y++){
			clown.push_back(max( y->second - arr[x].first, abs(arr[x].second - y->first) ) );
		}
	}
	
	sort(clown.begin(), clown.end());
	for (int x = 0; x < k; x++){
		if (x < clown.size()) cout << clown[x] << '\n';
		else cout << ans << '\n';
	}
}

Compilation message

road_construction.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main(){
      | ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:126:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |   if (x < clown.size()) cout << clown[x] << '\n';
      |       ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7120 KB Output is correct
2 Correct 48 ms 7184 KB Output is correct
3 Correct 41 ms 7168 KB Output is correct
4 Correct 43 ms 7168 KB Output is correct
5 Correct 47 ms 5932 KB Output is correct
6 Correct 6 ms 2396 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2531 ms 35672 KB Output is correct
2 Correct 2609 ms 35732 KB Output is correct
3 Correct 39 ms 6976 KB Output is correct
4 Correct 2037 ms 38292 KB Output is correct
5 Correct 1583 ms 38276 KB Output is correct
6 Correct 1629 ms 38640 KB Output is correct
7 Correct 1732 ms 37856 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5596 ms 33740 KB Output is correct
2 Correct 5791 ms 33916 KB Output is correct
3 Correct 2 ms 2140 KB Output is correct
4 Correct 1574 ms 34788 KB Output is correct
5 Correct 1452 ms 11840 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5596 ms 33740 KB Output is correct
2 Correct 5791 ms 33916 KB Output is correct
3 Correct 2 ms 2140 KB Output is correct
4 Correct 1574 ms 34788 KB Output is correct
5 Correct 1452 ms 11840 KB Output is correct
6 Correct 5540 ms 33928 KB Output is correct
7 Correct 5571 ms 33844 KB Output is correct
8 Correct 3 ms 2136 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 4614 ms 31884 KB Output is correct
11 Correct 1518 ms 34812 KB Output is correct
12 Correct 1441 ms 10576 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7120 KB Output is correct
2 Correct 48 ms 7184 KB Output is correct
3 Correct 41 ms 7168 KB Output is correct
4 Correct 43 ms 7168 KB Output is correct
5 Correct 47 ms 5932 KB Output is correct
6 Correct 6 ms 2396 KB Output is correct
7 Correct 1633 ms 19216 KB Output is correct
8 Correct 1619 ms 18916 KB Output is correct
9 Correct 40 ms 7124 KB Output is correct
10 Correct 1422 ms 17064 KB Output is correct
11 Correct 1326 ms 14704 KB Output is correct
12 Correct 456 ms 9532 KB Output is correct
13 Correct 545 ms 9704 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7120 KB Output is correct
2 Correct 48 ms 7184 KB Output is correct
3 Correct 41 ms 7168 KB Output is correct
4 Correct 43 ms 7168 KB Output is correct
5 Correct 47 ms 5932 KB Output is correct
6 Correct 6 ms 2396 KB Output is correct
7 Correct 2531 ms 35672 KB Output is correct
8 Correct 2609 ms 35732 KB Output is correct
9 Correct 39 ms 6976 KB Output is correct
10 Correct 2037 ms 38292 KB Output is correct
11 Correct 1583 ms 38276 KB Output is correct
12 Correct 1629 ms 38640 KB Output is correct
13 Correct 1732 ms 37856 KB Output is correct
14 Correct 5596 ms 33740 KB Output is correct
15 Correct 5791 ms 33916 KB Output is correct
16 Correct 2 ms 2140 KB Output is correct
17 Correct 1574 ms 34788 KB Output is correct
18 Correct 1452 ms 11840 KB Output is correct
19 Correct 5540 ms 33928 KB Output is correct
20 Correct 5571 ms 33844 KB Output is correct
21 Correct 3 ms 2136 KB Output is correct
22 Correct 2 ms 2396 KB Output is correct
23 Correct 4614 ms 31884 KB Output is correct
24 Correct 1518 ms 34812 KB Output is correct
25 Correct 1441 ms 10576 KB Output is correct
26 Correct 1633 ms 19216 KB Output is correct
27 Correct 1619 ms 18916 KB Output is correct
28 Correct 40 ms 7124 KB Output is correct
29 Correct 1422 ms 17064 KB Output is correct
30 Correct 1326 ms 14704 KB Output is correct
31 Correct 456 ms 9532 KB Output is correct
32 Correct 545 ms 9704 KB Output is correct
33 Correct 6557 ms 36924 KB Output is correct
34 Correct 5554 ms 41436 KB Output is correct
35 Correct 4319 ms 35484 KB Output is correct
36 Correct 1263 ms 21548 KB Output is correct
37 Correct 1285 ms 21596 KB Output is correct
38 Correct 1803 ms 17528 KB Output is correct