[11663번] 선분 위의 점

문제 출처 :

https://www.acmicpc.net/problem/11663

알고리즘 분석 :

문제 해결에 필요한 사항

1. lower_bound

이 문제는 선분에 점이 몇개 존재하는지 확인하면 된다.

n 제한이 10만이기에 그냥 탐색을 한다면 O(10만*10만)이기에 TLE이고

결국 NlgN으로 해결해야 하는데 이 방법을 lower_bound로 해결한다.

선분의 시작점에서 lower_bound를 통해 시작점 이상이 존재하는 인덱스를 찾아주고

이 인덱스 값이 점의 개수와 동일하다면 선분상에 점이 없다는 것이다.

선분의 끝점에서 lower_bound를 하고 만약 현재 인덱스 값이 끝점보다 더 크다면 -1을 해준다

그리고 마지막으로 인덱스 값을 -로 계산해주면 정답을 구할 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
vector<int> vc;
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
    
        vc.push_back(val);
    }
    sort(vc.begin(), vc.end());
 
    while (m--)
    {
        int s, e;
        scanf("%d %d", &s, &e);
 
        auto lo = lower_bound(vc.begin(), vc.end(), s);
        auto hi = lower_bound(vc.begin(), vc.end(), e);
        if (lo == vc.end())
        {
            printf("0\n");
            continue;
        }
 
        if (hi == vc.end())
            printf("%d\n", vc.size() - (lo - vc.begin()));
 
        else if (vc[hi - vc.begin()] > e)
        {
            hi--;
            printf("%d\n", (hi - vc.begin()) - (lo - vc.begin()) + 1);
        }
        else
            printf("%d\n", (hi - vc.begin()) - (lo - vc.begin()) + 1);
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>