oj.uz

Submission #386511

# Submission time Handle Problem Language Result Execution time Memory
386511 2021-04-06T17:14:17 Z MohamedAhmed04 Road Construction (JOI21_road_construction) C++14
65 / 100
 10000 ms 60448 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e5 + 10 ;

int X[MAX] , Y[MAX] , A[MAX] , B[MAX] ;
int n , k ;

pair<int , int> tree[4 * MAX] ;

void update(int node , int l , int r , int idx , int val)
{
	if(idx > r || idx < l)
		return ;
	if(l == r)
	{
		tree[node] = max(tree[node] , {val , idx}) ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , idx , val) ;
	update(node << 1 | 1 , mid+1 , r , idx , val) ;
	tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}

pair<int , int>query(int node , int l , int r , int from , int to)
{
	if(from > r || to < l)
		return {0 , 0} ;
	if(l >= from && r <= to)
		return tree[node] ;
	int mid = (l + r) >> 1 ;
	pair<int , int>p1 = query(node << 1 , l , mid , from , to) ;
	pair<int , int>p2 = query(node << 1 | 1 , mid+1 , r , from , to) ;
	return max(p1 , p2) ;
}

vector<int>v ;

void compress()
{
	for(int i = 1 ; i <= n ; ++i)
		v.push_back(A[i]) , v.push_back(B[i]) ;
	sort(v.begin() , v.end()) ;
	v.erase(unique(v.begin() , v.end()) , v.end()) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		A[i] = lower_bound(v.begin() , v.end() , A[i]) - v.begin() ;
		B[i] = lower_bound(v.begin() , v.end() , B[i]) - v.begin() ;
		A[i]++ , B[i]++ ;
	}
}

void preprocess()
{
	vector< pair<int , int> >vp ;
	for(int i = 1 ; i <= n ; ++i)
		vp.emplace_back(X[i] , Y[i]) ;
	sort(vp.begin() , vp.end()) ;
	for(int i = 1 ; i <= n ; ++i)
		X[i] = vp[i-1].first , Y[i] = vp[i-1].second ;
	for(int i = 1 ; i <= n ; ++i)
		A[i] = X[i] - Y[i] , B[i] = X[i] + Y[i] ;
	compress() ;
}

vector<long long>ans ;
set< pair<int , int> >s[MAX] ;
int curidx ;

void solve(int l , int r , long long x)
{
	if(l > r || ans.size() == k)
		return ;
	pair<int , int>p = query(1 , 1 , 2*n , l , r) ;
	if(p.first > 0 && v[p.first-1] >= x)
	{
		int idx = p.second ;
		for(auto it = s[idx].rbegin() ; it != s[idx].rend() && ans.size() < k ; it++)
		{
			p = (*it) ;
			if(v[p.first-1] < x)
				break ;
			ans.push_back(1ll * abs(X[curidx] - X[p.second]) + abs(Y[curidx] - Y[p.second])) ;
		}
		solve(l , idx-1 , x) ;
		solve(idx+1 , r , x) ;
	}
}

bool check(long long mid)
{
	ans.clear() ;
	memset(tree , 0 , sizeof(tree)) ;
	for(int i = 1 ; i <= 2*n ; ++i)
		s[i].clear() ;
	for(int i = 1 ; i <= n ; ++i)
	{
		int idx = lower_bound(v.begin() , v.end() , X[i] - mid - Y[i]) - v.begin() ;
		curidx = i ;
		solve(idx+1 , 2*n , X[i] - mid + Y[i]) ;
		update(1 , 1 , 2*n , A[i] , B[i]) ;
		s[A[i]].insert({B[i] , i}) ;
	}
	return (ans.size() == k) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>X[i]>>Y[i] ;
	preprocess() ;
	long long l = 1 , r = 4e9 ;
	long long ans2 = r ;
	while(l <= r)
	{
		long long mid = (l + r) >> 1ll ;
		if(check(mid))
			ans2 = mid , r = mid-1ll ;
		else
			l = mid+1ll ;
	}
	check(ans2-1) ;
	sort(ans.begin() , ans.end()) ;
	for(auto &i : ans)
		cout<<i<<"\n" ;
	for(int i = 0 ; i < k - (int)(ans.size()) ; ++i)
		cout<<ans2<<"\n" ;
	cout<<"\n" ;
	return 0 ;
}

Compilation message

road_construction.cpp: In function 'void solve(int, int, long long int)':
road_construction.cpp:76:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |  if(l > r || ans.size() == k)
      |              ~~~~~~~~~~~^~~~
road_construction.cpp:82:69: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |   for(auto it = s[idx].rbegin() ; it != s[idx].rend() && ans.size() < k ; it++)
      |                                                          ~~~~~~~~~~~^~~
road_construction.cpp: In function 'bool check(long long int)':
road_construction.cpp:108:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |  return (ans.size() == k) ;
      |          ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2083 ms 44260 KB Output is correct
2 Correct 2079 ms 44256 KB Output is correct
3 Correct 1799 ms 44404 KB Output is correct
4 Correct 1716 ms 44488 KB Output is correct
5 Correct 1346 ms 43064 KB Output is correct
6 Correct 102 ms 39660 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4676 ms 60376 KB Output is correct
2 Correct 4685 ms 60448 KB Output is correct
3 Correct 820 ms 44260 KB Output is correct
4 Correct 4793 ms 60248 KB Output is correct
5 Correct 4710 ms 60364 KB Output is correct
6 Correct 4683 ms 60364 KB Output is correct
7 Correct 4621 ms 59732 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9106 ms 57188 KB Output is correct
2 Correct 9486 ms 57144 KB Output is correct
3 Correct 87 ms 39532 KB Output is correct
4 Correct 3264 ms 57144 KB Output is correct
5 Correct 7853 ms 57144 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9106 ms 57188 KB Output is correct
2 Correct 9486 ms 57144 KB Output is correct
3 Correct 87 ms 39532 KB Output is correct
4 Correct 3264 ms 57144 KB Output is correct
5 Correct 7853 ms 57144 KB Output is correct
6 Correct 9254 ms 57144 KB Output is correct
7 Correct 9422 ms 57272 KB Output is correct
8 Correct 91 ms 39660 KB Output is correct
9 Correct 92 ms 39532 KB Output is correct
10 Correct 9592 ms 57260 KB Output is correct
11 Correct 3056 ms 57144 KB Output is correct
12 Correct 7834 ms 57144 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2083 ms 44260 KB Output is correct
2 Correct 2079 ms 44256 KB Output is correct
3 Correct 1799 ms 44404 KB Output is correct
4 Correct 1716 ms 44488 KB Output is correct
5 Correct 1346 ms 43064 KB Output is correct
6 Correct 102 ms 39660 KB Output is correct
7 Correct 8661 ms 50528 KB Output is correct
8 Correct 9061 ms 50528 KB Output is correct
9 Correct 1762 ms 44384 KB Output is correct
10 Correct 6001 ms 49892 KB Output is correct
11 Correct 6526 ms 49752 KB Output is correct
12 Correct 3181 ms 50576 KB Output is correct
13 Correct 3987 ms 49124 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2083 ms 44260 KB Output is correct
2 Correct 2079 ms 44256 KB Output is correct
3 Correct 1799 ms 44404 KB Output is correct
4 Correct 1716 ms 44488 KB Output is correct
5 Correct 1346 ms 43064 KB Output is correct
6 Correct 102 ms 39660 KB Output is correct
7 Correct 4676 ms 60376 KB Output is correct
8 Correct 4685 ms 60448 KB Output is correct
9 Correct 820 ms 44260 KB Output is correct
10 Correct 4793 ms 60248 KB Output is correct
11 Correct 4710 ms 60364 KB Output is correct
12 Correct 4683 ms 60364 KB Output is correct
13 Correct 4621 ms 59732 KB Output is correct
14 Correct 9106 ms 57188 KB Output is correct
15 Correct 9486 ms 57144 KB Output is correct
16 Correct 87 ms 39532 KB Output is correct
17 Correct 3264 ms 57144 KB Output is correct
18 Correct 7853 ms 57144 KB Output is correct
19 Correct 9254 ms 57144 KB Output is correct
20 Correct 9422 ms 57272 KB Output is correct
21 Correct 91 ms 39660 KB Output is correct
22 Correct 92 ms 39532 KB Output is correct
23 Correct 9592 ms 57260 KB Output is correct
24 Correct 3056 ms 57144 KB Output is correct
25 Correct 7834 ms 57144 KB Output is correct
26 Correct 8661 ms 50528 KB Output is correct
27 Correct 9061 ms 50528 KB Output is correct
28 Correct 1762 ms 44384 KB Output is correct
29 Correct 6001 ms 49892 KB Output is correct
30 Correct 6526 ms 49752 KB Output is correct
31 Correct 3181 ms 50576 KB Output is correct
32 Correct 3987 ms 49124 KB Output is correct
33 Execution timed out 10089 ms 59064 KB Time limit exceeded
34 Halted 0 ms 0 KB -