fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. /*#include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  7. /*find_by_order()and order_of_key(). */
  8.  
  9. #define ll          int
  10.  
  11. //#define test
  12.  
  13. #define mp          make_pair
  14. #define f           first
  15. #define s           second
  16. #define all(a)      a.begin(),a.end()
  17. #define pb          push_back
  18. #define vi          vector<int>
  19. #define pi          pair<int,int>
  20. #define pll         pair<ll,ll>
  21. #define vll         vector<ll>
  22.  
  23. const ll maxn  = 1e6+7;
  24. const ll mod  = 1e9+7;
  25. const ll MOD  = 1e9+7;
  26. #define inf         LLONG_MAX
  27. #define debug(a)    for(ll i=0;i<a.size();i++) cout<<a[i]<<" "; cout<<endl;       
  28.  
  29. //functions
  30. template <typename T1,typename T2>
  31. T1 pow_(const T1 &a,const T2 &b)
  32. {
  33.     if(!b) return 1;
  34.     T1 p = pow_(a,b/2);
  35.     p*=p;
  36.     return (b%2)?(p*a):p;
  37. }
  38.  
  39. template <typename T1,typename T2>
  40. T1 prod(const T1 &a,const T1 &b,const T2 &mod)
  41. {
  42.     return ((a%mod)*(b%mod))%mod;
  43. }
  44.  
  45. template <typename T1,typename T2,typename T3>
  46. T1 modpow(const T1 &a,const T2 &b,const T3 &mod)
  47. {
  48.     if(!b) return 1;
  49.     T1 p = modpow(a,b/2,mod);
  50.     p = prod(p,p,mod);
  51.     return (b%2)?(prod(p,a,mod)):p;
  52. }
  53.  
  54. template <typename T1,typename T2>
  55. T1 inv(T1 &x,T2 &MOD) {return modpow(x,MOD-2,MOD);}
  56.  
  57. struct Job
  58. {
  59. 	int start, finish, profit;
  60. };
  61.  
  62. // A utility function that is used for sorting events
  63. // according to finish time
  64. bool myfunction(Job s1, Job s2)
  65. {
  66. 	return (s1.finish < s2.finish);
  67. }
  68.  
  69. // A Binary Search based function to find the latest job
  70. // (before current job) that doesn't conflict with current
  71. // job. "index" is index of the current job. This function
  72. // returns -1 if all jobs before index conflict with it.
  73. // The array jobs[] is sorted in increasing order of finish
  74. // time.
  75. int binarySearch(Job jobs[], int index)
  76. {
  77. 	// Initialize 'lo' and 'hi' for Binary Search
  78. 	int lo = 0, hi = index - 1;
  79.  
  80. 	// Perform binary Search iteratively
  81. 	while (lo <= hi)
  82. 	{
  83. 		int mid = (lo + hi) / 2;
  84. 		if (jobs[mid].finish <= jobs[index].start)
  85. 		{
  86. 			if (jobs[mid + 1].finish <= jobs[index].start)
  87. 				lo = mid + 1;
  88. 			else
  89. 				return mid;
  90. 		}
  91. 		else
  92. 			hi = mid - 1;
  93. 	}
  94.  
  95. 	return -1;
  96. }
  97.  
  98. // The main function that returns the maximum possible
  99. // profit from given array of jobs
  100. int findMaxProfit(Job arr[], int n)
  101. {
  102. 	// Sort jobs according to finish time
  103. 	sort(arr, arr+n, myfunction);
  104.  
  105. 	// Create an array to store solutions of subproblems. table[i]
  106. 	// stores the profit for jobs till arr[i] (including arr[i])
  107. 	int *table = new int[n];
  108. 	table[0] = arr[0].profit;
  109.  
  110. 	// Fill entries in table[] using recursive property
  111. 	for (int i=1; i<n; i++)
  112. 	{
  113. 		// Find profit including the current job
  114. 		int inclProf = arr[i].profit;
  115. 		int l = binarySearch(arr, i);
  116. 		if (l != -1)
  117. 			inclProf += table[l];
  118.  
  119. 		// Store maximum of including and excluding
  120. 		table[i] = max(inclProf, table[i-1]);
  121. 	}
  122.  
  123. 	// Store result and free dynamic memory allocated for table[]
  124. 	int result = table[n-1];
  125. 	delete[] table;
  126.  
  127. 	return result;
  128. }
  129.  
  130.  
  131. void main_()
  132. {
  133. 	ll n,m;
  134. 	cin>>n>>m;
  135. 	Job arr[n];
  136. 	for(int i=0;i<n;i++)
  137. 	{
  138. 		cin>>arr[i].start>>arr[i].finish;
  139.  
  140. 		if(arr[i].start==arr[i].finish)
  141. 		{
  142. 			arr[i].start--;
  143. 			arr[i].finish++;
  144. 			arr[i].profit=1;
  145. 		}
  146. 		else arr[i].profit = arr[i].finish - arr[i].start;
  147. 		//if(arr[i].profit==0) arr[i].profit=1;
  148. 	}
  149. 	ll ans = m-findMaxProfit(arr,n);
  150. 	if(ans>0) cout<<ans<<endl;
  151. 	else cout<<0<<endl;
  152.  
  153. }
  154.  
  155. int main()
  156. {   
  157.     #ifdef test
  158.     ll t;
  159.     cin>>t;
  160.     while(t--) 
  161.     #endif
  162.     {
  163.         main_();
  164.     }
  165.     return 0;
  166. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
4 10
1 2
3 4
5 6
3 10
stdout
copy 
2
https://ideone.com/pNIIcE
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!