問題一覧 > 通常問題

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,,N の順列 p=(p1,p2,p3,,pN) が与えられます. p1,2,3,,N の順列の中で辞書順で何番目でしょうか?

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

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


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


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

入力

N
p1 p2 p3  pN
  • 1 行目には, 整数 N が与えられる.
  • 2 行目には, N 個の整数 p1,p2,p3,,pN が空白区切りで与えられます.

出力

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

制約

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

  • 1N100 000.
  • 1piN (1iN)
  • pipj (1i<jN)

サンプル

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。