fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. //_ ************************** Advanced PBDS ***********************************
  4.  
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10.  
  11. template<class T>
  12. using ordered_set = tree<
  13.     T,
  14.     null_type,
  15.     less<T>,
  16.     rb_tree_tag,
  17.     tree_order_statistics_node_update
  18. >;
  19.  
  20.  
  21. //_ ****************************************************************************
  22.  
  23. #define int              long long int
  24. #define double           long double
  25. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  26.  
  27.  
  28. const int M = 1000000007;
  29. const int N = 3e5+9;
  30. const int INF = 2e9+1;
  31. const int LINF = 2000000000000000001;
  32.  
  33. inline int power(int a, int b, int mod=M) {
  34.     int x = 1;
  35.     a %= mod;
  36.     while (b) {
  37.         if (b & 1) x = (x * a) % mod; 
  38.         a = (a * a) % mod;
  39.         b >>= 1;
  40.     }
  41.     return x;
  42. }
  43.  
  44.  
  45. //_ ***************************** START Below *******************************
  46.  
  47. // 8
  48. // 1 3
  49. // 2 4
  50. // 5 6
  51. // 6 7
  52. // 6 10
  53. // 7 8
  54. // 9 10
  55. // 11 12
  56.  
  57.  
  58. vector<pair<int,int>> a;
  59.  
  60. int consistency1(int n){
  61.  
  62. 	int maxi = 0;
  63.  
  64. 	for(int i=0; i<n; i++){
  65. 		int s = a[i].first;
  66. 		int e = a[i].second;
  67.  
  68. 		int ct = 0;
  69.  
  70. 		for(int j=0; j<n; j++){
  71.  
  72. 			int x = a[j].first;
  73. 			int y = a[j].second;
  74.  
  75. 			if(x <= s && y >= s) ct++;
  76. 			else if( x >= s && x <= e ) ct++;
  77.  
  78. 		}
  79.  
  80.  
  81. 		maxi = max(maxi, ct);
  82. 	}
  83.  
  84.  
  85. 	return n - maxi;
  86. }
  87.  
  88.  
  89.  
  90.  
  91. //* PBDS 
  92.  
  93. int consistency2(int n){
  94.     sort(begin(a), end(a));
  95.  
  96.     ordered_set<pair<int,int>> st;
  97.     int maxi = 0;
  98.  
  99.     for(int i = 0; i < n; i++){
  100.         int s = a[i].first;
  101.         int e = a[i].second;
  102.  
  103.         int left = st.size() - st.order_of_key({s, -INF});
  104.  
  105.         auto it = upper_bound(begin(a) + i + 1, end(a), make_pair(e, INF));
  106.         int right = it - (begin(a) + i + 1);
  107.  
  108.         st.insert({e, i});
  109.  
  110.         maxi = max(maxi, left + right + 1);
  111.     }
  112.  
  113.     return n - maxi;
  114. }
  115.  
  116.  
  117.  
  118. //* No PBDS 
  119.  
  120. int consistency3(int n) {
  121.     vector<int> starts(n), ends(n);
  122.     for(int i = 0; i < n; i++) {
  123.         starts[i] = a[i].first;
  124.         ends[i] = a[i].second;
  125.     }
  126.  
  127.     sort(starts.begin(), starts.end());
  128.     sort(ends.begin(), ends.end());
  129.  
  130.     int maxi = 0;
  131.  
  132.     for(int i = 0; i < n; i++) {
  133.         int s = a[i].first;
  134.         int e = a[i].second;
  135.  
  136.         // Count intervals that end strictly before the current one starts
  137.         int left_disjoint = lower_bound(ends.begin(), ends.end(), s) - ends.begin();
  138.  
  139.         // Count intervals that start strictly after the current one ends
  140.         int right_disjoint = starts.end() - upper_bound(starts.begin(), starts.end(), e);
  141.  
  142.         // Total intersecting = Total intervals - non-intersecting
  143.         int intersecting = n - left_disjoint - right_disjoint;
  144.  
  145.         maxi = max(maxi, intersecting);
  146.     }
  147.  
  148.     return n - maxi;
  149. }
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159. int practice(int n){
  160.  
  161.  
  162.     return 0;
  163. }
  164.  
  165.  
  166.  
  167.  
  168.  
  169. void solve() {
  170.  
  171.     int n;
  172.     cin>> n;
  173.  
  174.     a.resize(n);
  175.     for(int i=0; i<n; i++){
  176.     	int x, y;
  177.     	cin >> x >> y;
  178.     	a[i] = {x, y};
  179.     }
  180.  
  181.     cout << consistency1(n) << " " << consistency2(n) << " " << consistency3(n) << endl;
  182.  
  183.  
  184. }
  185.  
  186.  
  187.  
  188.  
  189.  
  190. int32_t main() {
  191.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  192.  
  193.     int t = 1;
  194.     // cin >> t;
  195.     while (t--) {
  196.         solve();
  197.     }
  198.  
  199.     return 0;
  200. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
8
1 3
2 4
5 6
6 7
6 10
7 8
9 10
11 12
stdout
copy 
3 3 3
https://ideone.com/iEga42
language:
C++14 (gcc 8.3)
created:
1 day 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!