별빛 관측소
실버 I의견: 0
별빛 관측소의 전파 망원경은 \(N\)개의 별에서 신호 세기를 측정했다. 우주 물리학자들은 두 별의 신호 세기 합이 특정 범위 \([S, T]\)에 들어오는 별의 쌍을 조사하고 싶다.
정수 배열 \(A\)가 주어질 때, \(i < j\)이고 \(S \le A_i + A_j \le T\)인 순서 쌍 \((i,\ j)\)의 개수를 구하여라.
- \(2 \le N \le 200\,000\)
- \(-2 \times 10^9 \le S \le T \le 2 \times 10^9\)
- 각 신호 세기는 \(-10^9\) 이상 \(10^9\) 이하의 정수이다.
첫째 줄에 별의 수 \(N\), 범위의 하한 \(S\), 상한 \(T\)가 공백으로 구분되어 주어진다.
둘째 줄에 각 별의 신호 세기 \(A_1, A_2, \ldots, A_N\)이 공백으로 구분되어 주어진다.
\(S \le A_i + A_j \le T\)인 쌍 \((i,\ j)\)(\(i < j\))의 수를 출력한다.
5 5 7
1 3 5 2 4
6
정렬하면 \([1,2,3,4,5]\)이다. 합이 \([5,7]\) 범위인 쌍: \((1,4)\to5\), \((1,5)\to6\), \((2,3)\to5\), \((2,4)\to6\), \((2,5)\to7\), \((3,4)\to7\) — 총 \(6\)쌍이다.
3 20 20
10 10 10
3
세 원소 중 임의의 두 원소를 고르면 합이 항상 \(20\)이다. 쌍의 수는 \(\binom{3}{2} = 3\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
별빛 관측소
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
별빛 관측소