제출 #386511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
386511		MohamedAhmed04	Road Construction (JOI21_road_construction)	C++14	65 / 100	10089 ms	60448 KiB

road_construction

#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 ;
}		

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 0 / 35