問題一覧 > 通常問題

No.1496 Mysterious Counting

レベル : / AI推定難易度 : 2050 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 42
作問者 : penguinman / テスター : kaage tpyneriver
お気に入りにしたユーザー ProblemId : 6191 / 自分の提出
問題文最終更新日: 2021-04-29 19:04:33
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 293 (順位表) の他の問題:

Problem Statement

You are given a permutation $P$ of length $N$. For each $i=1,\ 2,\ldots,\ N$, count the number of non-empty contiguous subarrays that satisfy both of the following conditions.

  • The minimum of the elements contained in the subarray is $i$.
  • The sum of the elements contained in the subarray is at most $A_i$.

Input

\(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)$
  • All inputs are integers.

Output

Print over $N$ lines.

On the $k$-th line, print the answer for $i=k$.

Sample

Sample 1
Input
3
2 1 3
3 2 2
Output
2
1
0

For example, when $i=1$, $(2,\ 1)$ and $(1)$ satisfy the conditions.

Sample 2
Input
9
8 5 4 7 2 1 3 6 9
40 38 6 27 21 39 42 25 26
Output
23
5
1
6
2
2
1
1
1
Sample 3
Input
10
8 6 4 5 2 10 1 3 7 9
5 15 17 38 27 34 46 13 9 27
Output
2
4
2
6
1
2
2
1
1
1

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