플래티넘 V설명
길이 \(N\)의 양의 정수 수열 \(a_1, \dots, a_N\) 과 정수 \(c\) 가 주어진다. 다음을 만족하는 순서쌍 \((i, j)\) 의 개수를 구하여라.
- \(i < j\)
- \(a_i > c \cdot a_j\)
\(c=1\) 이면 일반적인 역전이지만, 임의의 \(c\) 에 대해 일반화된 문제이다. \(N\)이 크므로 분할 정복으로 \(O(N \log N)\) 에 풀어야 한다.
제약
\(1 \le N \le 200{,}000\)
\(1 \le c \le 10^9\)
\(1 \le a_i \le 10^9\)
입력 형식
첫째 줄에 \(N\)과 \(c\)가 주어진다.
둘째 줄에 \(N\)개의 양의 정수 \(a_1, \dots, a_N\)이 주어진다.
출력 형식
조건을 만족하는 순서쌍의 개수를 출력한다.
예제 1
입력
5 2
9 4 3 1 8
출력
5설명
\(c=2\). \(a_i>2a_j\) 인 쌍: \((9,4)\) 는 \(9>8\), \((9,3)\) 는 \(9>6\), \((9,1)\) 은 \(9>2\), \((4,1)\) 은 \(4>2\), \((3,1)\) 은 \(3>2\). 총 5개이다.
예제 2
입력
3 1
1 2 3
출력
0설명
\(c=1\), 수열이 순증가하므로 \(a_i>a_j\) 인 쌍이 없어 답은 0이다.
문제 정보
riseoj 작성
출처 Original
태그