Problems
N개의 건초 더미가 일차원 도로의 이곳 저곳에 흩어져있다.
존은 건초 더미가 어느 지역에 있는지 파악하기 위하여 질문을 여러번 한다.
존이 좌표 A와 B에 대해 질문을 하면 A~B 사이에 있는 건초 더미의 개수를 알려주자.
Input
첫 번째 줄에 N과 Q가 입력된다. (1≤N≤100,000, 1≤Q≤100,000)
두 번째 줄에 N개의 건초 더미의 위치가 주어진다.
건초 더미의 위치는 0 이상 1,000,000,000 이하이다.
세 번째 줄부터 Q줄에 걸쳐 존이 질문하는 좌표 A와 B가 입력된다. (0≤A≤B≤1,000,000,000)
Output
Q줄에 걸쳐 존의 질문에 대한 답을 출력하시오.
Example
4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10
2
2
3
4
1
0
Source
USACO 2016 December Silver
You must sign in to write code.