Guest User

Untitled

a guest
Oct 19th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <memory.h>
  3. #include <assert.h>
  4. #include <curses.h>
  5.  
  6. /*
  7. * На числовой прямой окрасили N отрезков.
  8. * Известны координаты левого и правого концов каждого отрезка (Li и Ri).
  9. * Найти сумму длин частей числовой прямой, окрашенных ровно в один слой.
  10. */
  11.  
  12. struct ThickPoint{
  13. int point;
  14. int thickness;
  15. };
  16.  
  17. bool operator < (const ThickPoint &firstPoint, const ThickPoint &secondPoint){
  18. if (firstPoint.point == secondPoint.point){
  19. return firstPoint.thickness < secondPoint.thickness;
  20. }
  21. return firstPoint.point < secondPoint.point;
  22. }
  23.  
  24. template <class T>
  25. class isLess{
  26. public:
  27. bool operator () (const T & firstObject, const T & secondObject){
  28. return firstObject < secondObject;
  29. }
  30. };
  31.  
  32. template <class T, class Compare>
  33. void Merge(T *leftArray, size_t sizeOfLeftArray, T* rightArray, size_t sizeOfRightArray, T* buffer, Compare comp = isLess<T>()){
  34. size_t i = 0;
  35. size_t j = 0;
  36. while((i < sizeOfLeftArray) && (j < sizeOfRightArray)){
  37. if (comp( leftArray[i],rightArray[j])){
  38. buffer[i + j] = leftArray[i];
  39. i++;
  40. } else {
  41. buffer[i + j] = rightArray[j];
  42. j++;
  43. }
  44. }
  45. if (sizeOfLeftArray == i){
  46. while(j < sizeOfRightArray) {
  47. buffer[i + j] = rightArray[j];
  48. j++;
  49. }
  50. } else {
  51. while(i < sizeOfLeftArray){
  52. buffer[j + i] = leftArray[i];
  53. i++;
  54. }
  55. }
  56.  
  57.  
  58. };
  59.  
  60. template <class T, class Compare>
  61. void MergeSort(T *array, size_t size, Compare comparator = isLess<T>()){
  62. if (size > 1) {
  63. size_t leftLen = size / 2;
  64. size_t rightLen = size - leftLen;
  65. MergeSort(array, leftLen, comparator);
  66. MergeSort(array + leftLen, rightLen, comparator);
  67. T *newArray = new T[size];
  68. Merge(array, leftLen, array + leftLen, rightLen, newArray, comparator);
  69. memcpy(array, newArray, sizeof(T) * size);
  70. delete[] newArray;
  71. }
  72. };
  73.  
  74.  
  75. size_t countThickLength(ThickPoint * points, size_t size){
  76. MergeSort(points, size, isLess<ThickPoint>());
  77. size_t thickness = 0;
  78. size_t length = 0 ;
  79. for(size_t i = 0; i < size - 1; ++i){
  80. thickness += points[i].thickness;
  81. if (thickness == 1){
  82. length += points[i+1].point-points[i].point;
  83. }
  84. }
  85. return length;
  86. }
  87.  
  88.  
  89.  
  90. int main() {
  91. size_t size = 0;
  92. std::cin >> size;
  93. ThickPoint * points = new ThickPoint[2*size];
  94.  
  95. size_t i = 0;
  96. for(size_t i = 0;i<2*size;i++){
  97. std::cin>>points[i].point;
  98. if(i%2 == 0){
  99. points[i].thickness = 1;
  100. } else {
  101. points[i].thickness = -1;
  102. }
  103. }
  104.  
  105. std::cout << countThickLength(points, 2 * size);
  106. delete[] points;
  107. return 0;
  108. }
Add Comment
Please, Sign In to add comment