[ boj : 11663 ] 선분 위의 점

www.acmicpc.net/problem/11663

11663번: 선분 위의 점

문제 : 점들이 N개 주어지고 M개의 선분이 주어질때 각 선분들에 점들이 몇개가 포함되어있는지 구하시오

 

해설 : 각점들마다 일일이 l<=x<=r 인지 비교해주기에는 N=100000 이기 때문에 시간초과가 발생합니다. 따라서 이분탐색을 사용하는데 어떻게 사용해야될까요?

 

주어진 선분의 두 수를 각각 x,y라고 합시다. 그리고 정렬된 점들의 L=0 , R=N-1 이라고 하고 x,y에 대하여 각각 탐색을 진행합니다.

 

이때 주의할점은 선분의 시작점 x는 lower_bound 가 되고 y는 upper_bound 가 된다는 점을 꼭 주의해주세요. 또한, 선분이 어느 점도 포함하지 못하는 경우도 따로 예외처리를 해주셔야 됩니다.

 

#include<bits/stdc++.h>

using namespace std;

int n, m;
int A[100000];
int f(int x, int y);

int main()
{	
	ios::sync_with_stdio(false);
	cin.tie(0);
	int x, y;
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> A[i];
	sort(A, A + n);
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		if (y < A[0] || A[n - 1] < x)cout << 0 << "\n";
		else cout << f(x, y) << "\n";
	}
	return 0;
}
int f(int x, int y)
{
	int l = 0, r = n-1;
	int loc=0, roc=n-1;
	while (l <= r)
	{
		int m = (l + r) / 2;
		if (A[m] < x)
			l = m + 1;
		else {
			loc = m;
			r = m - 1;
		}
	}
	l = 0, r = n-1;
	while (l<=r)
	{
		int m = (l + r) / 2;
		if (A[m] > y)
			r = m - 1;
		else {
			roc = m;
			l = m + 1;
		}
	}
	return roc - loc + 1;
}