BOJ 8983 ) 사냥꾼 (C++)

8983번: 사냥꾼

lower_bound를 이용해서 풀었다. lower_bound는 해당 범위에서 key값보다 같거나 큰 값 중 가장 작은 값을 반환한다. 사대를 입력받고 오름차순으로 정렬한 후 동물의 위치(a,b)를 입력받을 때 마다 해당 동물을 잡을 수 있는 사대 위치의 최솟값(a+b-L), 최댓값(L+a-b)을 구한 후 lower_bound를 이용해 사대 배열에서 min 값보다 같거나 큰 값 중 가장 작은 값의 위치를 구한다. 만약 그러한 값이 없다면 end를 반환하므로 조건문에서 해당 경우를 체크해준다.  

#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;

int M, N;
ll L;

ll arr[111111];

int main(){
    cin>>M>>N>>L;

    for(int i=0;i<M;i++){
        cin>>arr[i];
    }
    sort(arr, arr+M);
    int x, y, ans=0;
    for(int i=0;i<N;i++){
        cin>>x>>y;
        if(y>L) continue;
        ll min=x+y-L;
        ll max=L+x-y;
        auto temp1 = lower_bound(arr, arr+M, min);

        if(temp1 !=arr+M && *temp1<=max) ans++;
    }
    cout<<ans;
}

예전에 풀어본 유형인데 왜 바로 풀이가 생각이 안나는건지..