oj.uz

Submission #386513

# Submission time Handle Problem Language Result Execution time Memory
386513 2021-04-06T17:33:59 Z MohamedAhmed04 Road Construction (JOI21_road_construction) C++14
5 / 100
 1477 ms 6504 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

#include <bits/stdc++.h>

using namespace std ;

const int inf = 2e9 + 10 ;
const int MAX = 25000 + 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 {-inf - 1 , -1} ;
	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]) ;
	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() ;
		A[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 , int x)
{
	if(l > r || ans.size() == k)
		return ;
	pair<int , int>p = query(1 , 1 , n , l , r) ;
	if(p.first >= x)
	{
		int idx = p.second ;
		for(auto it = s[idx].rbegin() ; it != s[idx].rend() && ans.size() < k ; it++)
		{
			p = (*it) ;
			if(p.first < 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() ;
	for(int i = 1 ; i <= n*4 ; ++i)
		tree[i] = {-inf - 1 , -1} ;
	for(int i = 1 ; i <= 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 , n , min(inf * 1ll , max(inf * -1ll , X[i] - mid + Y[i]))) ;
		update(1 , 1 , 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, 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:109:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |  return (ans.size() == k) ;
      |          ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1477 ms 6308 KB Output is correct
2 Correct 1411 ms 6376 KB Output is correct
3 Correct 1167 ms 6336 KB Output is correct
4 Correct 1053 ms 6504 KB Output is correct
5 Correct 1163 ms 5224 KB Output is correct
6 Correct 13 ms 1644 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 3308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 3308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 3308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1477 ms 6308 KB Output is correct
2 Correct 1411 ms 6376 KB Output is correct
3 Correct 1167 ms 6336 KB Output is correct
4 Correct 1053 ms 6504 KB Output is correct
5 Correct 1163 ms 5224 KB Output is correct
6 Correct 13 ms 1644 KB Output is correct
7 Runtime error 11 ms 3328 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1477 ms 6308 KB Output is correct
2 Correct 1411 ms 6376 KB Output is correct
3 Correct 1167 ms 6336 KB Output is correct
4 Correct 1053 ms 6504 KB Output is correct
5 Correct 1163 ms 5224 KB Output is correct
6 Correct 13 ms 1644 KB Output is correct
7 Runtime error 9 ms 3308 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -