Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.74 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. using std::cin;
  5.  
  6.  
  7. template<class T>
  8. class IsLessDefault{
  9. public:
  10.     bool operator ()(const T& l, const T& r){
  11.         return l < r;
  12.     }
  13. };
  14.  
  15.  
  16. struct Point{
  17. public:
  18.     int l;
  19.     int index;
  20.     Point():l(0),index(0){};
  21. };
  22.  
  23. bool IsLessPoint(const Point& l, const Point& r){
  24.     return l.l < r.l;
  25. }
  26.  
  27.  
  28. template <class T,class Compare = IsLessDefault<T> >
  29. void Merge(T* arr, int l, int r, T* res, Compare IsLess = Compare()){
  30.     int i = 0; int j = l;
  31.     int cnt = 0;
  32.     while(i < l && j < l+r){
  33.         if(IsLess(arr[i],arr[j]))
  34.             res[cnt++] = arr[i++];
  35.         else{
  36.             res[cnt++] = arr[j++];
  37.         }
  38.     }
  39.     while(i < l)
  40.         res[cnt++] = arr[i++];
  41.     while(j < l+r)
  42.         res[cnt++] = arr[j++];
  43. }
  44.  
  45.  
  46.  
  47. template <class T, class Compare = IsLessDefault<T> >
  48. void MergeSort(T* arr, int n, Compare IsLess = Compare()){
  49.     if(n <= 1)
  50.         return;
  51.     int l = n/2;
  52.     int r = n - n/2;
  53.     MergeSort(arr,l,IsLess);
  54.     MergeSort(arr + l,r,IsLess);
  55.     T* c = new T[n];
  56.     Merge(arr,l,r,c,IsLess);
  57.     memcpy(arr,c,sizeof(Point)*n);
  58.     delete[]c;
  59. }
  60.  
  61.  
  62.  
  63. int run(Point* points,int n){
  64.     MergeSort(points,n,IsLessPoint);
  65.     int result = 0;
  66.     int k = 0;
  67.     for(int i = 0; i < n;i++){
  68.         if(k > 0){
  69.             result += points[i].l - points[i-1].l;
  70.         }
  71.         k+= points[i].index;
  72.     }
  73.     return result;
  74. }
  75.  
  76.  
  77. int main(){
  78.     int n = 0;
  79.     cin >> n;
  80.     Point* points = new Point[n*2];
  81.     for(int i = 0; i < n*2; i++){
  82.         cin >> points[i].l;
  83.         points[i].index = (i %2 == 0 ? 1:-1);
  84.     }
  85.     int result = run(points,n*2);
  86.     std::cout << result << std::endl;
  87.     delete[] points;
  88.     return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement