Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int MaxInArray(vector<pair<int, int>> numbers) {
- int max = numbers[0].first;
- for (int i = 1; i < numbers.size(); i++)
- if (max < numbers[i].first)
- max = numbers[i].first;
- return max;
- }
- int MinInArray(vector<pair<int, int>> numbers) {
- int min = numbers[0].first;
- for (int i = 1; i < numbers.size(); i++)
- if (min > numbers[i].first)
- min = numbers[i].first;
- return min;
- }
- void countingSort(vector<pair<int, int>> numbers)
- {
- int max = MaxInArray(numbers);
- int min = MinInArray(numbers);
- int k = max - min + 1;
- int* c = new int[k];
- vector<pair<int, int>> b(numbers.size());
- for (int i = 0; i < k; ++i)
- c[i] = 0;
- for (int i = 0; i < numbers.size(); ++i)
- c[numbers[i].first - min]++;
- for (int j = 1; j < k; ++j)
- c[j] = c[j] + c[j - 1];
- for (int i = numbers.size() - 1; i >= 0; --i)
- {
- c[numbers[i].first - min]--;
- b[c[numbers[i].first - min]] = numbers[i];
- }
- delete[] c;
- for (int i = 0; i < numbers.size(); i++)
- numbers[i] = b[i];
- }
- int Search_Binary(vector<pair<int, int>> numbers, int left, int right, int key)
- {
- int mid = 0;
- while (1)
- {
- mid = (left + right) / 2;
- if (key < numbers[mid].first)
- right = mid - 1;
- else if (key > numbers[mid].first&& key > numbers[mid].second)
- left = mid + 1;
- else
- return mid;
- if (left > right || left >= numbers.size())
- return -1;
- }
- }
- int main()
- {
- int n, k, start, end, index, x, count = 0, j = 0, p = 0;
- vector<pair<int, int>> vec;
- cin >> n;
- for (int i = 0; i < n; i++)
- {
- cin >> start >> end;
- vec.push_back(make_pair(start, end));
- }
- countingSort(vec);
- cin >> k;
- for (int i = 0; i < k; i++)
- {
- cin >> x;
- index = Search_Binary(vec, 0, vec.size(), x);
- if (index != -1)
- {
- count++;
- j = index - 1;
- p = index + 1;
- while (j >= 0 && x >= vec[j].first && x <= vec[j].second)
- {
- count++;
- j--;
- }
- while (p < vec.size() && x >= vec[p].first && x <= vec[p].second)
- {
- count++;
- p++;
- }
- }
- cout << count << endl;
- count = 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment