問題一覧 > 通常問題

No.1525 Meximum Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 18
作問者 : ChipppppChippppp / テスター : MtSakaMtSaka
1 ProblemId : 6102 / 自分の提出
問題文最終更新日: 2021-05-29 00:26:56

問題文

集合 $\{0, 1, \dots, N - 1\}$ の要素を並び替えた順列 $A = (A_1, A_2, \dots, A_N)$ が与えられます.
$\displaystyle \sum_{l = 1} ^ {N} \sum_{r = l} ^ {N} mex(A_{l}, A_{l+1}, \dots, A_{r})$
を求めてください.ただし,$mex(S)$ を $S$ に含まれない最小の非負整数とします.

入力

$N$
$A_1 \quad A_2 \quad \dots \quad A_N$

  • $1 \le N \le 2 \times 10 ^ 5$
  • $A$ は集合 $\{0, 1, \dots, N - 1\}$ の要素を並び替えた数列である.
  • 入力は全て整数
  • 出力

    $\displaystyle \sum_{l = 1} ^ {N} \sum_{r = l} ^ {N} mex(A_{l}, A_{l+1}, \dots, A_{r})$
    を一行に出力してください. また,最後に改行を出力してください.

    サンプル

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

    $l = 1$ のとき,$mex(0) + mex(0, 2) + mex(0, 2, 1) = 5$
    $l = 2$ のとき,$mex(2) + mex(2, 1) = 0$
    $l = 3$ のとき,$mex(1) = 0$
    よって,$5 + 0 + 0 = 5$ です.

    サンプル2
    入力
    10
    9 6 8 5 1 0 3 2 4 7
    出力
    112

    サンプル3
    入力
    15
    12 9 4 6 5 2 0 1 7 13 10 14 8 11 3
    出力
    197

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