問題一覧 > 通常問題

No.3469 ジャッジ結果の逆転数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 39
作問者 : yuki2006
ProblemId : 2161 / yukicoder 2026新ジャッジ contest (順位表) / 自分の提出
問題文最終更新日: 2026-03-06 22:31:39
yukicoder 2026新ジャッジ contestの他の問題:

問題文

あるオンラインジャッジに $N$ 個の提出が順番に行われました。これらの提出はそれぞれ別のジャッジサーバーに割り当てられ、提出 $i$ の実行時間は $A_i$ ミリ秒です。

提出 $i$ が提出 $j$ より先に提出された（$i < j$）にもかかわらず、実行時間が長い（$A_i > A_j$）ため結果の返却順が逆転するとき、これを逆転と呼びます。

逆転の回数を求めてください。

入力

$N$
$A_1\ A_2\ \ldots\ A_N$
制約はすべて整数。
  • $1 \le N \le 200{,}000$
  • $1 \le A_i \le 10^9$

出力

逆転の回数を 1 行で出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4
3 1 4 1
出力
3

提出 1 (3ms) と提出 2 (1ms): 提出 2 が先に返る → 逆転
提出 1 (3ms) と提出 4 (1ms): 提出 4 が先に返る → 逆転
提出 3 (4ms) と提出 4 (1ms): 提出 4 が先に返る → 逆転

サンプル2
入力
3
1 2 3
出力
0

実行時間が提出順に短い順なので、逆転は起きません。

サンプル3
入力
3
3 2 1
出力
3

すべてのペアで逆転が起きています。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。