fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. bool compare(const pair<int, char> &p1, const pair<int, char> &p2)
  9. {
  10. 	return p1.first < p2.first;
  11. }
  12.  
  13. vector<pair<int, int>> func(const vector<pair<int, char>> &lists)
  14. {
  15. 	int seg = 0, n = lists.size();
  16. 	vector<pair<int, int>> res;
  17. 	for (int i = 0; i < n; ++i) {
  18. 		if (lists[i].second == 'l') ++seg;
  19. 		else if (lists[i].second == 'r') --seg;
  20. 		else res.push_back(make_pair(lists[i].first, seg));
  21. 	}
  22. 	return res;
  23. }
  24.  
  25. int binarySearch(const vector<pair<int, int>> &arr, int left, int right, int key)
  26. {
  27. 	if (left > right) return -1;
  28. 	else if (left == right) return arr[left].first == key ? left : -1;
  29. 	else {
  30. 		int mid = (left + right) / 2;
  31. 		if (arr[mid].first == key) return mid;
  32. 		else if (key < arr[mid].first) return binarySearch(arr, left, mid - 1, key);
  33. 		else return binarySearch(arr, mid + 1, right, key);
  34. 	}
  35. }
  36.  
  37. int main()
  38. {
  39. 	int s, p, a, b, pos;
  40. 	cin >> s >> p;
  41. 	vector<pair<int, char>> lists;
  42. 	vector<int> points(p);
  43. 	for (int i = 0; i < s; ++i) {
  44. 		cin >> a >> b;
  45. 		lists.push_back(make_pair(a, 'l'));
  46. 		lists.push_back(make_pair(b, 'r'));
  47. 	}
  48. 	for (int i = 0; i < p; ++i) {
  49. 		cin >> points[i];
  50. 		lists.push_back(make_pair(points[i], 'p'));
  51. 	}
  52. 	sort(lists.begin(), lists.end(), compare);
  53. 	vector<pair<int, int>> res = func(lists);
  54. 	for (int i = 0; i < p; ++i) {
  55. 		pos = binarySearch(res, 0, res.size() - 1, points[i]);
  56. 		cout << res[pos].second << " ";
  57. 	}
  58. 	return 0;
  59. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
3 3
2 3
3 4
4 5
2 3 4
stdout 
1 1 1
https://ideone.com/iMVpX2
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!