AmidamaruZXC

Untitled

Jan 30th, 2020
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int MaxInArray(vector<pair<int, int>> numbers) {
  7.     int max = numbers[0].first;
  8.     for (int i = 1; i < numbers.size(); i++)
  9.         if (max < numbers[i].first)
  10.             max = numbers[i].first;
  11.     return max;
  12. }
  13.  
  14. int MinInArray(vector<pair<int, int>> numbers) {
  15.     int min = numbers[0].first;
  16.     for (int i = 1; i < numbers.size(); i++)
  17.         if (min > numbers[i].first)
  18.             min = numbers[i].first;
  19.     return min;
  20. }
  21.  
  22. int MaxInArray2(vector<pair<int, int>> numbers) {
  23.     int max = numbers[0].second;
  24.     for (int i = 1; i < numbers.size(); i++)
  25.         if (max < numbers[i].second)
  26.             max = numbers[i].second;
  27.     return max;
  28. }
  29.  
  30. int MinInArray2(vector<pair<int, int>> numbers) {
  31.     int min = numbers[0].second;
  32.     for (int i = 1; i < numbers.size(); i++)
  33.         if (min > numbers[i].second)
  34.             min = numbers[i].second;
  35.     return min;
  36. }
  37.  
  38. void countingSort(vector<pair<int, int>>& numbers)
  39. {
  40.     int max = MaxInArray(numbers);
  41.     int min = MinInArray(numbers);
  42.     int k = max - min + 1;
  43.     int* c = new int[k];
  44.     vector<pair<int, int>> b(numbers.size());
  45.     for (int i = 0; i < k; ++i)
  46.         c[i] = 0;
  47.     for (int i = 0; i < numbers.size(); ++i)
  48.         c[numbers[i].first - min]++;
  49.     for (int j = 1; j < k; ++j)
  50.         c[j] = c[j] + c[j - 1];
  51.     for (int i = numbers.size() - 1; i >= 0; --i)
  52.     {
  53.         c[numbers[i].first - min]--;
  54.         b[c[numbers[i].first - min]] = numbers[i];
  55.     }
  56.     delete[] c;
  57.     for (int i = 0; i < numbers.size(); i++)
  58.         numbers[i] = b[i];
  59. }
  60.  
  61. void countingSort2(vector<pair<int, int>>& numbers)
  62. {
  63.     int max = MaxInArray2(numbers);
  64.     int min = MinInArray2(numbers);
  65.     int k = max - min + 1;
  66.     int* c = new int[k];
  67.     vector<pair<int, int>> b(numbers.size());
  68.     for (int i = 0; i < k; ++i)
  69.         c[i] = 0;
  70.     for (int i = 0; i < numbers.size(); ++i)
  71.         c[numbers[i].second - min]++;
  72.     for (int j = 1; j < k; ++j)
  73.         c[j] = c[j] + c[j - 1];
  74.     for (int i = numbers.size() - 1; i >= 0; --i)
  75.     {
  76.         c[numbers[i].second - min]--;
  77.         b[c[numbers[i].second - min]] = numbers[i];
  78.     }
  79.     delete[] c;
  80.     for (int i = 0; i < numbers.size(); i++)
  81.         numbers[i] = b[i];
  82. }
  83.  
  84. int Search_Binary(vector<pair<int, int>> numbers, int key)
  85. {
  86.     int left = 0;
  87.     int right = numbers.size() - 1;
  88.     if (left == right)
  89.         return left;
  90.     while (1)
  91.     {
  92.         if (right - left == 1)
  93.         {
  94.             if (numbers[left].first <= key && numbers[left].second >= key)
  95.                 return left;
  96.             else if (numbers[right].first <= key && numbers[right].second >= key)
  97.                 return right;
  98.             else return -1;
  99.         }
  100.         else
  101.         {
  102.             int middle = left + (right - left) / 2;
  103.             if (numbers[middle].first <= key && numbers[middle].second >= key)
  104.                 return middle;
  105.             if (numbers[middle].second < key)
  106.                 left = middle;
  107.             if (numbers[middle].first > key)
  108.                 right = middle;
  109.         }
  110.     }
  111. }
  112.  
  113. int main()
  114. {
  115.     int n, k, start, end, index, x, count = 0, j = 0, p = 0;
  116.     vector<pair<int, int>> vec;
  117.     cin >> n;
  118.     for (int i = 0; i < n; i++)
  119.     {
  120.         cin >> start >> end;
  121.         vec.push_back(make_pair(start, end));
  122.     }
  123.     countingSort(vec);
  124.     countingSort2(vec);
  125.     //cout << endl;
  126.     //for (int i = 0; i < vec.size(); i++)
  127.         //cout << vec[i].first << " " << vec[i].second << endl;
  128.     cin >> k;
  129.     for (int i = 0; i < k; i++)
  130.     {
  131.         cin >> x;
  132.         index = Search_Binary(vec, x);
  133.         if (index != -1)
  134.         {
  135.             if (x >= vec[index].first && x <= vec[index].second)
  136.                 count++;
  137.             j = index - 1;
  138.             p = index + 1;
  139.             while (j >= 0 && x >= vec[j].first && x <= vec[j].second)
  140.             {
  141.                 count++;
  142.                 j--;
  143.             }
  144.             while (p < vec.size() && x >= vec[p].first && x <= vec[p].second)
  145.             {
  146.                 count++;
  147.                 p++;
  148.             }
  149.         }
  150.         cout << count << endl;
  151.         count = 0;
  152.     }
  153. }
Advertisement
Add Comment
Please, Sign In to add comment