fork download 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define endl "\n"
  4. #define pb push_back
  5. #define INF 1234567890
  6. #define MOD 1000000007
  7. #define PI atan(1)/4
  8. #define mp make_pair
  9. #define REP(i,n) for (int i = 0; i < n; i++)
  10. #define FOR(i,a,b) for (int i = a; i <=b; i++)
  11. #define REPD(i,n) for (int i = n-1; i >= 0; i--)
  12. #define all(v) v.begin(),v.end()
  13. #define pii pair<int,int>
  14. #define F first
  15. #define S second
  16. #define mii map<int,int>
  17. #define vi vector<int>
  18. #define vvi vector<vi>
  19. #define itr :: iterator it
  20. #define WL(t) while(t --)
  21. #define gcd(a,b) __gcd((a),(b))
  22. #define lcm(a,b) ((a)*(b))/gcd((a),(b))
  23. #define print(x) cout << x << "\n";
  24. #define debug(x) cout << x << "\n";
  25. #define debug2(x,y) cout << x << " " << y << "\n";
  26. #define debug3(x,y,z) cout << x << " " << y << " " << z << "\n";
  27. #define debug4(x,y,z,zz) cout << x << " " << y << " " << z <<" "<<zz << "\n";
  28. #define debug5(x,y,z,zz,yy) cout << x << " " << y << " " << z <<" "<<zz << " "<< yy << "\n";
  29. #define ONLINE_JUDGE 54
  30.  
  31. /* AUTHOR : Jagreet 'v01d' Das Gupta */
  32.  
  33. using namespace std;
  34.  
  35. void solve();
  36. signed main()
  37. {
  38. 	#ifndef ONLINE_JUDGE
  39. 	freopen("../input.txt","r",stdin);
  40. 	freopen("../output.txt","w",stdout);
  41. 	#else
  42. 	ios_base::sync_with_stdio(false);
  43. 	cin.tie(NULL);
  44. 	#endif
  45. 	int t = 1;
  46. 	//cin >> t;
  47. 	WL(t) solve();
  48. }
  49.  
  50. void solve()
  51. {
  52. 	int n;
  53. 	cin >> n;
  54. 	pii intervals[n];
  55. 	REP(i,n) cin >> intervals[i].S >> intervals[i].F;
  56. 	sort(intervals,intervals+n);
  57. 	set<int> added;
  58. 	REP(i,n)
  59. 	{
  60. 		bool exist = false;
  61. 		int a = intervals[i].S;
  62. 		int b = intervals[i].F;
  63. 		auto ii = lower_bound(all(added),a);
  64. 		auto jj = lower_bound(all(added),b);
  65. 		for(auto it = ii;it!=jj;it++)
  66. 		{
  67. 			int x = *it;
  68. 			if(x>=a&&x<=b)
  69. 			{
  70. 				exist = true;
  71. 				break;
  72. 			}
  73. 		}
  74. 		if(!exist)
  75. 		{
  76. 			added.insert(b);
  77. 		}
  78. 	}
  79. 	print(added.size());
  80. }
Success #stdin #stdout 0s 15240KB
comments ()
stdin 
3 
6 9 
3 5 
4 8
stdout 
2
https://ideone.com/qpgyr7
language:
C++14 (gcc 8.3)
created:
6 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!