oj.uz

Submission #386515

# Submission time Handle Problem Language Result Execution time Memory
386515 2021-04-06T17:37:45 Z MohamedAhmed04 Road Construction (JOI21_road_construction) C++14
65 / 100
 10000 ms 39916 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 = 250000 + 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} ;
	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 , long long x)
{
	if(l > r || ans.size() == k)
		return ;
	pair<int , int>p = query(1 , 1 , n , l , r) ;
	if(p.second != -1 && 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} ;
	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 , 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, 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: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 1419 ms 16872 KB Output is correct
2 Correct 1422 ms 16884 KB Output is correct
3 Correct 1116 ms 16872 KB Output is correct
4 Correct 1068 ms 17004 KB Output is correct
5 Correct 1149 ms 15848 KB Output is correct
6 Correct 24 ms 12268 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4217 ms 39916 KB Output is correct
2 Correct 4201 ms 39880 KB Output is correct
3 Correct 694 ms 16872 KB Output is correct
4 Correct 4290 ms 39736 KB Output is correct
5 Correct 4217 ms 39788 KB Output is correct
6 Correct 4183 ms 39856 KB Output is correct
7 Correct 4091 ms 39224 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7702 ms 36720 KB Output is correct
2 Correct 7982 ms 36604 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 2770 ms 36604 KB Output is correct
5 Correct 7497 ms 36604 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7702 ms 36720 KB Output is correct
2 Correct 7982 ms 36604 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 2770 ms 36604 KB Output is correct
5 Correct 7497 ms 36604 KB Output is correct
6 Correct 7828 ms 36724 KB Output is correct
7 Correct 8061 ms 36604 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 8 ms 12140 KB Output is correct
10 Correct 8208 ms 36664 KB Output is correct
11 Correct 2623 ms 36536 KB Output is correct
12 Correct 7476 ms 36664 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1419 ms 16872 KB Output is correct
2 Correct 1422 ms 16884 KB Output is correct
3 Correct 1116 ms 16872 KB Output is correct
4 Correct 1068 ms 17004 KB Output is correct
5 Correct 1149 ms 15848 KB Output is correct
6 Correct 24 ms 12268 KB Output is correct
7 Correct 7402 ms 25868 KB Output is correct
8 Correct 7305 ms 25868 KB Output is correct
9 Correct 1038 ms 17000 KB Output is correct
10 Correct 5069 ms 25300 KB Output is correct
11 Correct 5766 ms 25112 KB Output is correct
12 Correct 2670 ms 25840 KB Output is correct
13 Correct 3539 ms 24484 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1419 ms 16872 KB Output is correct
2 Correct 1422 ms 16884 KB Output is correct
3 Correct 1116 ms 16872 KB Output is correct
4 Correct 1068 ms 17004 KB Output is correct
5 Correct 1149 ms 15848 KB Output is correct
6 Correct 24 ms 12268 KB Output is correct
7 Correct 4217 ms 39916 KB Output is correct
8 Correct 4201 ms 39880 KB Output is correct
9 Correct 694 ms 16872 KB Output is correct
10 Correct 4290 ms 39736 KB Output is correct
11 Correct 4217 ms 39788 KB Output is correct
12 Correct 4183 ms 39856 KB Output is correct
13 Correct 4091 ms 39224 KB Output is correct
14 Correct 7702 ms 36720 KB Output is correct
15 Correct 7982 ms 36604 KB Output is correct
16 Correct 8 ms 12140 KB Output is correct
17 Correct 2770 ms 36604 KB Output is correct
18 Correct 7497 ms 36604 KB Output is correct
19 Correct 7828 ms 36724 KB Output is correct
20 Correct 8061 ms 36604 KB Output is correct
21 Correct 9 ms 12140 KB Output is correct
22 Correct 8 ms 12140 KB Output is correct
23 Correct 8208 ms 36664 KB Output is correct
24 Correct 2623 ms 36536 KB Output is correct
25 Correct 7476 ms 36664 KB Output is correct
26 Correct 7402 ms 25868 KB Output is correct
27 Correct 7305 ms 25868 KB Output is correct
28 Correct 1038 ms 17000 KB Output is correct
29 Correct 5069 ms 25300 KB Output is correct
30 Correct 5766 ms 25112 KB Output is correct
31 Correct 2670 ms 25840 KB Output is correct
32 Correct 3539 ms 24484 KB Output is correct
33 Execution timed out 10083 ms 38572 KB Time limit exceeded
34 Halted 0 ms 0 KB -