oj.uz

Submission #386507

# Submission time Handle Problem Language Result Execution time Memory
386507 2021-04-06T16:52:09 Z MohamedAhmed04 Road Construction (JOI21_road_construction) C++14
11 / 100
 10000 ms 60372 KB 
#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 - 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:74:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |  if(l > r || ans.size() == k)
      |              ~~~~~~~~~~~^~~~
road_construction.cpp:80:69: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |   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:106:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |  return (ans.size() == k) ;
      |          ~~~~~~~~~~~^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:131:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |  for(int i = 0 ; i < k - ans.size() ; ++i)
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2777 ms 44384 KB Output is correct
2 Correct 2648 ms 44268 KB Output is correct
3 Correct 2348 ms 44244 KB Output is correct
4 Correct 2264 ms 44380 KB Output is correct
5 Correct 1864 ms 43104 KB Output is correct
6 Correct 106 ms 39660 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6041 ms 60364 KB Output is correct
2 Correct 6066 ms 60364 KB Output is correct
3 Correct 1268 ms 44188 KB Output is correct
4 Correct 6134 ms 60236 KB Output is correct
5 Correct 6022 ms 60372 KB Output is correct
6 Correct 5997 ms 60364 KB Output is correct
7 Correct 5935 ms 59832 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9950 ms 57144 KB Output is correct
2 Execution timed out 10082 ms 57272 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9950 ms 57144 KB Output is correct
2 Execution timed out 10082 ms 57272 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2777 ms 44384 KB Output is correct
2 Correct 2648 ms 44268 KB Output is correct
3 Correct 2348 ms 44244 KB Output is correct
4 Correct 2264 ms 44380 KB Output is correct
5 Correct 1864 ms 43104 KB Output is correct
6 Correct 106 ms 39660 KB Output is correct
7 Execution timed out 10071 ms 48492 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2777 ms 44384 KB Output is correct
2 Correct 2648 ms 44268 KB Output is correct
3 Correct 2348 ms 44244 KB Output is correct
4 Correct 2264 ms 44380 KB Output is correct
5 Correct 1864 ms 43104 KB Output is correct
6 Correct 106 ms 39660 KB Output is correct
7 Correct 6041 ms 60364 KB Output is correct
8 Correct 6066 ms 60364 KB Output is correct
9 Correct 1268 ms 44188 KB Output is correct
10 Correct 6134 ms 60236 KB Output is correct
11 Correct 6022 ms 60372 KB Output is correct
12 Correct 5997 ms 60364 KB Output is correct
13 Correct 5935 ms 59832 KB Output is correct
14 Correct 9950 ms 57144 KB Output is correct
15 Execution timed out 10082 ms 57272 KB Time limit exceeded
16 Halted 0 ms 0 KB -