[BOJ14170] Counting Haybales

문제

• N(1<= <=100,000)개의 건초가 1차원 도로에 배치
• q개의 쿼리에 대해서 특정 구간에 건초 몇 개 있는지 검사

입력

• N, Q
• N 개의 다른 정수 (0<= <=1,000,000,000)
• 다음 Q 줄에 건초 개수 찾을 구간 A, B (0<= <=1,000,000,000)

설계

• 처음엔, n을 배열 인덱으로 담아 건초가 있는지 없는지 체크하는 방식으로 풀었음
• n최대가 10억인데, 당연히 시간초과 남
• STL 중 lower_bound, upper_bound 이용
• 그냥 순서대로 n을 배열에 담기
• sort하여 오름차순으로 정렬
• A, B에 해당하는 값을 찾아(lower_bound) 인덱스 빼주기
• b는 upper_bound를 이용해 찾아도 되고, 내 코드는 lower_bound에서 b+1을 하여 b값을 가진 인덱스의 다음 값을 도출

피드백

• lower_bound : 찾고 싶은 값 이상의 iter 반환
• upper_bound : 찾고 싶은 값 초과의 iter 반환
• 둘 다 iterator를 반환하기 때문에, 인덱스를 반환 받기 위해 해당 배열 빼기
• 어차피 둘의 값을 빼는 거라 iter - iter 하면 정수가 반환되기는 함

How I solved(click to github)

---

ref :
BOJ14170