AmidamaruZXC

Untitled

Jan 29th, 2020
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 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.  
  23. void countingSort(vector<pair<int, int>>& numbers)
  24. {
  25.     int max = MaxInArray(numbers);
  26.     int min = MinInArray(numbers);
  27.     int k = max - min + 1;
  28.     int* c = new int[k];
  29.     vector<pair<int, int>> b(numbers.size());
  30.     for (int i = 0; i < k; ++i)
  31.         c[i] = 0;
  32.     for (int i = 0; i < numbers.size(); ++i)
  33.         c[numbers[i].first - min]++;
  34.     for (int j = 1; j < k; ++j)
  35.         c[j] = c[j] + c[j - 1];
  36.     for (int i = numbers.size() - 1; i >= 0; --i)
  37.     {
  38.         c[numbers[i].first - min]--;
  39.         b[c[numbers[i].first - min]] = numbers[i];
  40.     }
  41.     delete[] c;
  42.     for (int i = 0; i < numbers.size(); i++)
  43.         numbers[i] = b[i];
  44. }
  45.  
  46. int Search_Binary(vector<pair<int, int>> numbers, int key)
  47. {
  48.     int left = 0;
  49.     int right = numbers.size() - 1;
  50.     if (left == right)
  51.         return left;
  52.     while (1)
  53.     {
  54.         if (right - left == 1)
  55.         {
  56.             if (numbers[left].first <= key && numbers[left].second >= key)
  57.                 return left;
  58.             else if (numbers[right].first <= key && numbers[right].second >= key)
  59.                 return right;
  60.             else return -1;
  61.         }
  62.         else
  63.         {
  64.             int middle = left + (right - left) / 2;
  65.             if (numbers[middle].first <= key && numbers[middle].second >= key)
  66.                 return middle;
  67.             if (numbers[middle].second < key)
  68.                 left = middle;
  69.             if (numbers[middle].first > key)
  70.                 right = middle;
  71.         }
  72.     }
  73. }
  74.  
  75. int main()
  76. {
  77.     int n, k, start, end, index, x, count = 0, j = 0, p = 0;
  78.     vector<pair<int, int>> vec;
  79.     cin >> n;
  80.     for (int i = 0; i < n; i++)
  81.     {
  82.         cin >> start >> end;
  83.         vec.push_back(make_pair(start, end));
  84.     }
  85.     countingSort(vec);
  86.     cin >> k;
  87.     for (int i = 0; i < k; i++)
  88.     {
  89.         cin >> x;
  90.         index = Search_Binary(vec, x);
  91.         if (index != -1)
  92.         {
  93.             if (x >= vec[index].first && x <= vec[index].second)
  94.                 count++;
  95.             j = index - 1;
  96.             p = index + 1;
  97.             while (j >= 0 && x >= vec[j].first)
  98.             {
  99.                 if (x >= vec[j].first && x <= vec[j].second)
  100.                     count++;
  101.                 j--;
  102.             }
  103.             while (p < vec.size() && x >= vec[p].first)
  104.             {
  105.                 if (x >= vec[p].first && x <= vec[p].second)
  106.                     count++;
  107.                 p++;
  108.             }
  109.         }
  110.         cout << count << endl;
  111.         count = 0;
  112.     }
  113. }
Advertisement
Add Comment
Please, Sign In to add comment