레이팅 미적용설명
농부 존은 방금 자신의 건초 더미 \(N\)개(\(1 \leq N \leq 100,000\))를 농장을 가로지르는 1차원 도로 위의 여러 지점에 배치했다. 건초 더미들이 적절한 간격으로 놓였는지 확인하려는 존을 위해 \(Q\)개의 질의(\(1 \leq Q \leq 100,000\))에 답해 주자. 각 질의는 도로 위의 특정 구간 안에 있는 건초 더미의 개수를 묻는다.
문제 출제: 닉 우(Nick Wu)
제약
문제 출제: 닉 우(Nick Wu)
입력 형식
첫째 줄에 \(N\)과 \(Q\)가 주어진다.
다음 줄에는 \(0 \ldots 1,000,000,000\) 범위의 서로 다른 정수 \(N\)개가 주어지며, 각 위치에 건초 더미가 하나씩 있다는 뜻이다.
다음 \(Q\)개의 줄에는 두 정수 \(A\)와 \(B\)(\(0 \leq A \leq B \leq 1,000,000,000\))가 주어지며, 이는 \(A\) 이상 \(B\) 이하 구간에 있는 건초 더미의 개수를 묻는 질의이다.
출력 형식
\(Q\)개의 줄을 출력한다. 각 질의에 대해 해당 구간에 있는 건초 더미의 개수를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
haybales.in · 출력을 쓸 파일 haybales.out예제 1
입력
4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10출력
2
2
3
4
1
0문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > December > Silver
태그