問題一覧 > 通常問題

No.1496 不思議な数え上げ

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 27
作問者 : penguinmanpenguinman / テスター : kaagekaage tpynerivertpyneriver
8 ProblemId : 6191 / 出題時の順位表
問題文最終更新日: 2021-04-29 19:04:33

問題文

長さ $N$ の順列 $P$ が与えられます。$i=1,\ 2,\ldots,\ N$ について、以下の条件を両方とも満たす空でない連続した部分列の個数を数えてください。

  • 部分列に含まれる要素の最小値が $i$
  • 部分列に含まれる要素の総和が $A_i$ 以下

入力

\(N\)
\(P_1\) \(P_2\) \(\ldots\) \(P_N\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

  • $1\leq N\leq 2\times 10^5$
  • $1\leq P_i\leq N$
  • $1\leq A_i\leq \frac{N(N+1)}{2}$
  • $P_i\neq P_j\ (i\neq j)$
  • 入力は全て整数

出力

$N$ 行に渡って出力してください。

$k$ 行目には、$i=k$ の場合の答えを出力してください。

サンプル

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

例えば $i=1$ のとき、$(2,\ 1)$ と $(1)$ が条件を満たします。

サンプル2
入力
9
8 5 4 7 2 1 3 6 9
40 38 6 27 21 39 42 25 26
出力
23
5
1
6
2
2
1
1
1
サンプル3
入力
10
8 6 4 5 2 10 1 3 7 9
5 15 17 38 27 34 46 13 9 27
出力
2
4
2
6
1
2
2
1
1
1

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