No.3469 Number of Inversions in Judge Results
yuki2006Problem Statement
$N$ submissions were made in order to an online judge. Each of these submissions is assigned to a different judge server, and the execution time of submission $i$ is $A_i$ milliseconds.
When submission $i$ was submitted before submission $j$ ($i < j$) but its execution time is longer ($A_i > A_j$), so that the order in which the results are returned is reversed, this is called an inversion.
Find the number of inversions.
Input
$N$ $A_1\ A_2\ \ldots\ A_N$All constraints are integers.
- $1 \le N \le 200{,}000$
- $1 \le A_i \le 10^9$
Output
Output the number of inversions on one line.
Print a newline at the end.
Sample
Sample 1
Input
4 3 1 4 1
Output
3
Submission 1 (3ms) and submission 2 (1ms): submission 2 returns first → inversion
Submission 1 (3ms) and submission 4 (1ms): submission 4 returns first → inversion
Submission 3 (4ms) and submission 4 (1ms): submission 4 returns first → inversion
Sample 2
Input
3 1 2 3
Output
0
The execution times are in ascending order of submission, so no inversions occur.
Sample 3
Input
3 3 2 1
Output
3
Inversions occur in all pairs.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。