[백준 14170] Counting Haybales

www.acmicpc.net/problem/14170

14170번: Counting Haybales

USACO 2016 December Silver 문제이다.

풀이를 보고 나면 어렵지 않은데 처음 봤을 땐 당황스러웠다.

 

문제 내용은 쿼리로 주어지는 구간에 haybales가 몇 개인지 세는 문제이다.

정렬을 한다해도 직접 체크했다간 TLE가 발생할 수 있다.

upper_bound와 lower_bound를 사용하면 쉽게 답을 도출할 수 있다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n, q;
int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> n >> q;
  vector<int> v(n);
  for (int i = 0; i < n; i++)
  {
    cin >> v[i];
  }
  sort(v.begin(), v.end());

  for (int i = 0; i < q; i++)
  {
    int left, right;
    cin >> left >> right;
    int p1 = upper_bound(v.begin(), v.end(), right) - v.begin();
    int p2 = lower_bound(v.begin(), v.end(), left) - v.begin();
    cout << p1 - p2 << "\n";
  }
  return 0;
}