레이팅 미적용농부 존의 \(N\)마리(\(N \leq 3 \times 10^5\)) 소들의 키는 \(1, 2, \ldots, N\)이다. 어느 날, 소들은 어떤 순서로 한 줄로 서서 프리스비를 하고 있다. 이 순서대로의 소들의 키를 \(h_1 \ldots h_N\)이라고 하자(따라서 \(h\)는 \(1 \ldots N\)의 순열이다).
줄에서 위치 \(i\)와 \(j\)에 있는 두 소는, 둘 사이의 모든 소의 키가 \(\min(h_i, h_j)\)보다 낮을 때에만 프리스비를 성공적으로 주고받을 수 있다.
프리스비를 성공적으로 주고받을 수 있는 소 쌍이 있는 모든 위치 쌍 \(i
출제자: Quanquan Liu
배점
- 테스트 케이스 1-3은 \(N\le 5000\)을 만족한다.
- 테스트 케이스 4-11은 추가 제약이 없다.
출제자: Quanquan Liu
입력의 첫째 줄에 정수 \(N\)이 주어진다. 다음 줄에 \(h_1 \ldots h_N\)이 공백으로 구분되어 주어진다.
프리스비를 주고받을 수 있는 소들이 있는 모든 위치 쌍의 거리의 합을 출력한다. 이 문제에 등장하는 정수의 크기가 크므로 64비트 정수 자료형(예: C/C++의 "long long")을 사용해야 할 수 있음에 유의하라.
7
4 3 1 2 5 6 724The pairs of successful locations in this example are as follows:
(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > January > Silver