fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. vector <pair<int,int> > v; // vector to stor pairs of position,power
  5. int n;
  6.  
  7. int dest [100010]; /* dest[i] stores the number of beacons destroyed if all
  8. 					beacons upto i+1 had been destroyed by additional beacon */
  9.  
  10. bool cmp(pair<int,int> l, pair <int,int> r)
  11. {
  12. 	return(l.first< r.first);
  13. }
  14. int bsearch(int k)
  15. {
  16. 	int low = 0;
  17. 	int high = k;
  18. 	int mid = high;
  19. 	while(low<=high)
  20. 	{
  21. 		mid = (low+high)/2;
  22. 		int gap = v[k].first - v[mid].first;
  23. 		if(gap < v[k].second)
  24. 			high = mid-1;
  25. 		if(gap > v[k].second)
  26. 			low = mid+1;
  27. 		if(gap == v[k].second)
  28. 		{
  29. 			break;
  30. 		}
  31. 	}
  32. 	return mid;
  33. }
  34.  
  35. inline void activate(int k)
  36. {	
  37. 	/* do a binary search to get the max number beacons destroyed.
  38. 	If still beacons are left, we activate the beacon and add its already 
  39. 	calculated destroy count to current beacon
  40. 	*/ 
  41. 	int pwreach = bsearch(k);
  42. 	dest[k] = k-pwreach;
  43. 	if(pwreach>0)
  44. 		dest[k] += dest[pwreach-1];
  45. }
  46.  
  47. int main()
  48. {
  49. 	ios_base::sync_with_stdio(false);
  50. 	cin >> n;	
  51. 	int pos,pwr;
  52. 	for(int i = 0; i < n ; ++i)
  53. 	{
  54. 		cin >> pos >>pwr;
  55. 	    v.push_back(make_pair(pos,pwr));	
  56. 	}
  57. 	sort(v.begin(),v.end(),cmp);
  58.  
  59. 	for(int i = 1; i < n; ++i)
  60. 	{
  61. 		/* Activation of the 0th (array index) beacon will destroy none. So we 
  62. 		begin by activating the first beacon*/
  63. 		activate(i);
  64. 	}
  65. 	int mdest = dest[n-1];
  66. 	for(int i = n-2;i >=0; --i)
  67. 	{
  68. 		/* we begin from the end, assuming all beacons upto i+1 had been 
  69. 		destroyed */
  70. 		if((dest[i] + n-i-1) < mdest)
  71. 			mdest = dest[i]+n-i-1;
  72. 	}
  73. 	cout << mdest << "\n";
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 3844KB
comments (?)
stdin
copy 
4
1 9
3 1
6 1
7 4
stdout
copy 
1
https://ideone.com/Y0yoHq
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!