Guest User

Untitled

a guest
Jul 23rd, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <set>
  7.  
  8.  
  9. using namespace std;
  10.  
  11. int sol ;
  12.  
  13. struct event{
  14.     int x , ind, tip ;
  15.     event( int _x = 0, int _ind = 0, int _tip = 0 ){
  16.     x = _x; ind = _ind; tip = _tip;
  17.     }
  18. };
  19.  
  20. vector <event> v ;
  21. int a , b , n ;
  22.  
  23. bool cmp ( event a , event b ){
  24.     if ( a.x == b.x ) return a.ind < b.ind ;
  25.     else return a.x < b.x ;
  26. }
  27.  
  28. set <int> s ;
  29.  
  30. void checkset (){
  31.     if ( s.size() == 1 ) sol++;
  32. }
  33. int t ;
  34.  
  35.  
  36. int main () {
  37. scanf("%d",&t);
  38. for( int x = 0 ; x < t ; ++x ){
  39.     scanf("%d",&n);
  40.     for( int i = 0 ; i < n ; ++i ){
  41.         scanf("%d%d",&a,&b);
  42.         v.push_back(event(a,i,0));
  43.         v.push_back(event(b,i,1));
  44.     }
  45.     sort ( v.begin(), v.end(),cmp);
  46.     for( int i = 0 ; i < v.size () ; ++i ){
  47.         if ( v[i].tip == 0 ){
  48.             s.insert(v[i].ind);
  49.         }
  50.         else{
  51.             s.erase(v[i].ind);
  52.         }
  53.         checkset();
  54.     }
  55.     printf("%d\n",sol);
  56.     v.clear();
  57. }
  58.     return 0;
  59. }
Add Comment
Please, Sign In to add comment