No.1496 Mysterious Counting
レベル :
/ AI推定難易度 : 2050
/ 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 :
penguinman
/ テスター :
kaage
tpyneriver
タグ : / 解いたユーザー数 42
作問者 :
penguinman
/ テスター :
kaage
tpyneriver
問題文最終更新日: 2021-04-29 19:04:33
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。