Advertisement
Guest User

Untitled

a guest
Dec 17th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.94 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. struct Cpoint {
  7. int point;
  8. char BeginOrEnd;
  9. };
  10.  
  11. template <typename Iterator>
  12. void SiftDown(Iterator i, Iterator begin, Iterator end)
  13. {
  14. Iterator left;
  15. Iterator right;
  16. if (2 * distance(begin, i) + 1 < distance(begin, end)) {
  17. left = i + distance(begin, i) + 1;
  18. }
  19. else {
  20. left = end;
  21. };
  22. if (2 * distance(begin, i) + 1 < distance(begin, end)) {
  23. right = i + distance(begin, i) + 2;
  24. }
  25. else {
  26. right = end;
  27. };
  28. Iterator largest = i;
  29. if (left < end && (*left).point > (*i).point)
  30. largest = left;
  31. if (right < end && (*right).point > (*largest).point)
  32. largest = right;
  33. if (largest != i) {
  34. swap(*i, *largest);
  35. SiftDown(largest, begin, end);
  36. }
  37. };
  38.  
  39. template <typename Iterator>
  40. void BuildHeap(Iterator begin, Iterator end)
  41. {
  42. Iterator i = end - distance(begin, end) / 2 - 1;
  43. while (i >= begin) {
  44. SiftDown(i, begin, end);
  45. if (i == begin) {
  46. break;
  47. };
  48. i--;
  49. }
  50. };
  51.  
  52. template <typename iterator>
  53. void HeapSort(iterator begin, iterator end) {
  54. int heapSize = distance(begin, end);
  55. BuildHeap(begin, end - 1);
  56. while (heapSize > 1) {
  57. heapSize--;
  58. swap(*begin, *(end - 1));
  59. end--;
  60. SiftDown(begin, begin, end);
  61. }
  62. }
  63.  
  64. int main()
  65. {
  66. int n = 0;
  67. cin >> n;
  68. vector <Cpoint> line;
  69. for (int i = 0; i < n; i++) {
  70. Cpoint element;
  71. cin >> element.point;
  72. element.BeginOrEnd = 'B';
  73. line.push_back(element);
  74. cin >> element.point;
  75. element.BeginOrEnd = 'E';
  76. line.push_back(element);
  77. };
  78. HeapSort(line.begin(), line.end());
  79. int sum = 0;
  80. int stapleBalance = 1;
  81. int test = 0;
  82. for (int i = 1; i < 2 * n; i++) {
  83. if (line[i].BeginOrEnd == 'B') {
  84. stapleBalance++;
  85. }
  86. else {
  87. stapleBalance--;
  88. };
  89. if (test == 0) {
  90. sum = sum + line[i].point - line[i - 1].point;
  91. };
  92. test = 0;
  93. if (stapleBalance == 0) {
  94. test = 1;
  95. };
  96. };
  97. cout << sum;
  98. //hhh
  99. return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement