fork download 
  1. #include <bits/stdc++.h>
  2. //#include <ext/pb_ds/assoc_container.hpp>
  3. //#include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. //using namespace __gnu_pbds;
  7.  
  8. //typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  9.  
  10. const int MAX_N = 1e5 + 5;
  11. const int MAX_L = 20; // ~ Log N
  12. const long long MOD = 1e9 + 7;
  13. const long long INF = 1e9 + 7;
  14.  
  15. typedef short unsigned int sui; // 0 to 65,535
  16. typedef int i; // -2147483648 to 2147483647
  17. typedef unsigned int ui; // 0 to 4294967295
  18. typedef unsigned long int uli; // 0 to 4,294,967,295
  19. typedef long long ll; //range -(2^63) to (2^63)-1
  20. typedef unsigned long long ull;
  21.  
  22. typedef vector<int> vi; 
  23. typedef pair<int, int> ii; 
  24. typedef vector<ii> vii;
  25. typedef vector<vi> vvi;
  26.  
  27. struct node {
  28.     ui a;
  29.     ui d;
  30. };
  31.  
  32. #define LSOne(S) (S & (-S))
  33. #define isBitSet(S, i) ((S >> i) & 1)
  34.  
  35.  
  36.  
  37. int cmp( node x, node y ){
  38.     return x.a < y.a;
  39. }
  40.  
  41. bool trackEmpty(vi track, int a){
  42.     bool flag = false;
  43.     if(track.empty()){
  44.         return true;
  45.     }
  46.     else{
  47.         for( auto i = track.begin(); i < track.end(); i++){
  48.             if ( *i < a ){
  49.                 track.erase(i);
  50.                 flag = true;
  51.                 break;
  52.             }
  53.         }
  54.         return flag;
  55.     }
  56. }
  57.  
  58. int main()
  59. {
  60.     ios_base::sync_with_stdio(0);
  61.     cin.tie(0);
  62.     cout.tie(0);
  63.  
  64.  
  65.     ull n; 
  66.     cin >> n;
  67.  
  68.     node train[n];
  69.     for (ull t = 0; t<n ; t++){
  70.         cin >> train[t].a >> train[t].d;
  71.         train[t].d = train[t].a + train[t].d;
  72.     }
  73.  
  74.     sort(train, train+n, cmp);
  75.     vi track;
  76.     ui maxSize = 1;
  77.     for(auto i: train){
  78.         if(trackEmpty(track, i.a)){
  79.             track.push_back(i.d);
  80.         }
  81.         else{
  82.             track.push_back(i.d);
  83.             maxSize = max(maxSize, static_cast<unsigned int> (track.size()));
  84.         }
  85.     }
  86.     cout << maxSize;
  87.     return 0;
  88. }
Success #stdin #stdout 0s 4692KB
comments (?)
stdin 
3 10 2 5 10 13 5
stdout 
2
https://ideone.com/jni51Y
language:
C++ (gcc 8.3)
created:
5 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!