Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct Cpoint {
- int point;
- char BeginOrEnd;
- };
- template <typename Iterator>
- void SiftDown(Iterator i, Iterator begin, Iterator end)
- {
- Iterator left;
- Iterator right;
- if (2 * distance(begin, i) + 1 < distance(begin, end)) {
- left = i + distance(begin, i) + 1;
- }
- else {
- left = end;
- };
- if (2 * distance(begin, i) + 1 < distance(begin, end)) {
- right = i + distance(begin, i) + 2;
- }
- else {
- right = end;
- };
- Iterator largest = i;
- if (left < end && (*left).point > (*i).point)
- largest = left;
- if (right < end && (*right).point > (*largest).point)
- largest = right;
- if (largest != i) {
- swap(*i, *largest);
- SiftDown(largest, begin, end);
- }
- };
- template <typename Iterator>
- void BuildHeap(Iterator begin, Iterator end)
- {
- Iterator i = end - distance(begin, end) / 2 - 1;
- while (i >= begin) {
- SiftDown(i, begin, end);
- if (i == begin) {
- break;
- };
- i--;
- }
- };
- template <typename iterator>
- void HeapSort(iterator begin, iterator end) {
- int heapSize = distance(begin, end);
- BuildHeap(begin, end - 1);
- while (heapSize > 1) {
- heapSize--;
- swap(*begin, *(end - 1));
- end--;
- SiftDown(begin, begin, end);
- }
- }
- int main()
- {
- int n = 0;
- cin >> n;
- vector <Cpoint> line;
- for (int i = 0; i < n; i++) {
- Cpoint element;
- cin >> element.point;
- element.BeginOrEnd = 'B';
- line.push_back(element);
- cin >> element.point;
- element.BeginOrEnd = 'E';
- line.push_back(element);
- };
- HeapSort(line.begin(), line.end());
- int sum = 0;
- int stapleBalance = 1;
- int test = 0;
- for (int i = 1; i < 2 * n; i++) {
- if (line[i].BeginOrEnd == 'B') {
- stapleBalance++;
- }
- else {
- stapleBalance--;
- };
- if (test == 0) {
- sum = sum + line[i].point - line[i - 1].point;
- };
- test = 0;
- if (stapleBalance == 0) {
- test = 1;
- };
- };
- cout << sum;
- //hhh
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement