No.2950 Max Min Product
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : nouka28 / テスター : rotti_coder t9unkubj
タグ : / 解いたユーザー数 25
作問者 : nouka28 / テスター : rotti_coder t9unkubj
問題文最終更新日: 2024-10-18 06:39:00
問題文
長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられるので以下の値を $998244353$ で割ったあまり求めてください。
$\displaystyle \sum_{l=1}^{N}\sum_{r=l}^{N}{\max(A_l,A_{l+1},\dots,A_r)\times \min(A_l,A_{l+1},\dots,A_r)}$
制約
- $1\leq N\leq 2\times 10^5$
- $1\leq A_i\leq 10^9$
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。$N$ $A_1$ $A_2$ $\dots$ $A_N$
出力
答えを出力せよ。
サンプル
サンプル1
入力
4 2 1 3 2
出力
38
$A$ の連続部分列は以下の $10$ 通りあります。
- $\max(A_1)\times\min(A_1)=2\times 2=4$
- $\max(A_2)\times\min(A_2)=1\times 1=1$
- $\max(A_3)\times\min(A_3)=3\times 3=9$
- $\max(A_4)\times\min(A_4)=2\times 2=4$
- $\max(A_1,A_2)\times\min(A_1,A_2)=2\times 1=2$
- $\max(A_2,A_3)\times\min(A_2,A_3)=3\times 1=3$
- $\max(A_3,A_4)\times\min(A_3,A_4)=3\times 2=6$
- $\max(A_1,A_2,A_3)\times\min(A_1,A_2,A_3)=3\times 1=3$
- $\max(A_2,A_3,A_4)\times\min(A_2,A_3,A_4)=3\times 1=3$
- $\max(A_1,A_2,A_3,A_4)\times\min(A_1,A_2,A_3,A_4)=3\times 1=3$
$\displaystyle \sum_{l=1}^{4}\sum_{r=l}^{4}{\max(A_l,A_{l+1},\dots,A_r)\times \min(A_l,A_{l+1},\dots,A_r)}=4+1+9+4+2+3+6+3+3+3=38$ なので $38$ を $998244353$ で割った余りの $38$ が答えになります。
サンプル2
入力
1 1
出力
1
サンプル3
入力
10 283946572 281630273 475961938 982637405 293709717 192730741 789163287 987382638 182630462 567839465
出力
771208723
$998244353$ で割った余りを求めてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。