AmidamaruZXC

Untitled

Jan 29th, 2020
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.15 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 left, int right, int key)
  47. {
  48.     int mid = 0;
  49.     while (1)
  50.     {
  51.         mid = (left + right) / 2;
  52.  
  53.         if (key < numbers[mid].first)      
  54.             right = mid - 1;      
  55.         else if (key > numbers[mid].first&& key > numbers[mid].second)
  56.             left = mid + 1;  
  57.         else                    
  58.             return mid;          
  59.  
  60.         if (left > right || left >= numbers.size())          
  61.             return -1;
  62.     }
  63. }
  64.  
  65. int main()
  66. {
  67.     int n, k, start, end, index, x, count = 0, j = 0, p = 0;
  68.     vector<pair<int, int>> vec;
  69.     cin >> n;
  70.     for (int i = 0; i < n; i++)
  71.     {
  72.         cin >> start >> end;
  73.         vec.push_back(make_pair(start, end));
  74.     }
  75.     countingSort(vec);
  76.     cin >> k;
  77.     for (int i = 0; i < k; i++)
  78.     {
  79.         cin >> x;
  80.         index = Search_Binary(vec, 0, vec.size(), x);
  81.         if (index != -1)
  82.         {
  83.             count++;
  84.             j = index - 1;
  85.             p = index + 1;
  86.             while (j >= 0 && x >= vec[j].first && x <= vec[j].second)
  87.             {
  88.                 count++;
  89.                 j--;
  90.             }
  91.             while (p < vec.size() && x >= vec[p].first && x <= vec[p].second)
  92.             {
  93.                 count++;
  94.                 p++;
  95.             }
  96.         }
  97.         cout << count << endl;
  98.         count = 0;
  99.     }
  100. }
Advertisement
Add Comment
Please, Sign In to add comment