問題一覧 > 通常問題

No.696 square1001 and Permutation 5

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : square1001square1001 / テスター : PulmnPulmn
1 ProblemId : 2125 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-05-19 20:42:16

問題文

2168 年, John と Brus は JOI に出場しており, 彼らは本選で全完し優勝しました. なので, John と Brus は JOI 春合宿で 4 位以内を取り, IOI の日本代表になると予想されていました.

しかし, 残念ながら 2 人とも春合宿で失敗してしまい, 同じ点数で 4 位を取ってしまいました. JOI 春合宿は 4 日間ありますが, 4 日間すべて同じ点数でした. 本選も両方全完していて同じ点数なので, なんと「最後の決闘」で代表選手を決めることになってしまいました!


最後の決闘では, 次のような問題が出されました. John と Brus は, 最後の望みをかけて, この問題を解こうとしました.

  • $1, 2, 3, \cdots, N$ の順列 $p = (p_1, p_2, p_3, \cdots, p_N)$ が与えられます. $p$ は $1, 2, 3, \cdots, N$ の順列の中で辞書順で何番目でしょうか?

John と Brus はこの問題の解法が分かり, 実装をして, コードのバグを直しました. 2 時間が経ち, そして, 両方がこの問題を正解しました. しかし, Brus より John の方が 1 秒だけ早く提出していたのです!

したがって, John が日本代表に選ばれました. かわいそうな Brus, 残念ながら IOI 日本代表に選ばれず, なんと彼は刑務所に入れられてしましました!


あなたは John と Brus のストーリーを聞きました. さて, この問題を 2 時間以内に解いて彼らより実力が高いことを証明してみましょう!


問題文の元ネタ:SRM 719 Div1 Hard - RedemptionOfMatthew99

入力

$N$
$p_1 \ p_2 \ p_3 \ \cdots \ p_N$
  • $1$ 行目には, 整数 $N$ が与えられる.
  • $2$ 行目には, $N$ 個の整数 $p_1, p_2, p_3, \cdots, p_N$ が空白区切りで与えられます.

出力

$p$ が $1, 2, 3, \cdots, N$ の順列の中で辞書順で何番目なのかを, $1$ 行で出力してください.

制約

すべての入力データは以下の制約を満たす.

  • $1 \le N \le 100 \ 000$.
  • $1 \leq p_i \leq N \ (1 \leq i \leq N)$
  • $p_i \neq p_j \ (1 \leq i < j \leq N)$

サンプル

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

これより辞書順で小さい $1, 2, 3$ の順列は, $(1, 2, 3), (1, 3, 2), (2, 1, 3)$ の $3$ つなので, $(2, 3, 1)$ は辞書順で $4$ 番目です.

サンプル2
入力
5
3 1 5 4 2
出力
54

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