A16366 | Berserk Monsters
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Monocarp is playing a computer game (yet again). Guess what is he doing? That's right, killing monsters.
There are $n$ monsters in a row, numbered from $1$ to $n$ . The $i$ -th monster has two parameters: attack value equal to $a_i$ and defense value equal to $d_i$ . In order to kill these monsters, Monocarp put a berserk spell on them, so they're attacking each other instead of Monocarp's character.
The fight consists of $n$ rounds. Every round, the following happens:
- first, every alive monster $i$ deals $a_i$ damage to the closest alive monster to the left (if it exists) and the closest alive monster to the right (if it exists);
- then, every alive monster $j$ which received more than $d_j$ damage during this round dies. I. e. the $j$ -th monster dies if and only if its defense value $d_j$ is strictly less than the total damage it received this round.
For each round, calculate the number of monsters that will die during that round.
There are $n$ monsters in a row, numbered from $1$ to $n$ . The $i$ -th monster has two parameters: attack value equal to $a_i$ and defense value equal to $d_i$ . In order to kill these monsters, Monocarp put a berserk spell on them, so they're attacking each other instead of Monocarp's character.
The fight consists of $n$ rounds. Every round, the following happens:
- first, every alive monster $i$ deals $a_i$ damage to the closest alive monster to the left (if it exists) and the closest alive monster to the right (if it exists);
- then, every alive monster $j$ which received more than $d_j$ damage during this round dies. I. e. the $j$ -th monster dies if and only if its defense value $d_j$ is strictly less than the total damage it received this round.
For each round, calculate the number of monsters that will die during that round.
输入格式
The first line contains one integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.
Each test case consists of three lines:
- the first line contains one integer $n$ ( $1 \le n \le 3 \cdot 10^5$ );
- the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ );
- the third line contains $n$ integers $d_1, d_2, \dots, d_n$ ( $1 \le d_i \le 10^9$ ).
Additional constraint on the input: the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$ .
Each test case consists of three lines:
- the first line contains one integer $n$ ( $1 \le n \le 3 \cdot 10^5$ );
- the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ );
- the third line contains $n$ integers $d_1, d_2, \dots, d_n$ ( $1 \le d_i \le 10^9$ ).
Additional constraint on the input: the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$ .
输出格式
For each test case, print $n$ integers. The $i$ -th integer should be equal to the number of monsters that die during the $i$ -th round.
输入输出样例
输入 #1
3 5 3 4 7 5 10 4 9 1 18 1 2 2 1 1 3 4 1 1 2 4 3 3 4 2
输出 #1
3 1 0 0 0 0 0 1 1 1 0
Explanation for the first test case of the example:
During the first round, the following happens:
- the monster $1$ deals $3$ damage to the monster $2$ ;
- the monster $2$ deals $4$ damage to the monster $1$ and the monster $3$ ;
- the monster $3$ deals $7$ damage to the monster $2$ and the monster $4$ ;
- the monster $4$ deals $5$ damage to the monster $3$ and the monster $5$ ;
- the monster $5$ deals $10$ damage to the monster $4$ ;
- the monster $1$ does not die, since it received $4$ damage and its defense is $4$ ;
- the monster $2$ dies, since it received $10$ damage and its defense is $9$ ;
- the monster $3$ dies, since it received $9$ damage and its defense is $1$ ;
- the monster $4$ does not die, since it received $17$ damage and its defense is $18$ ;
- the monster $5$ dies, since it received $5$ damage and its defense is $1$ .
After the first round, the monsters $1$ and $4$ stay alive.
During the second round, the following happens:
- the monster $1$ deals $3$ damage to the monster $4$ ;
- the monster $4$ deals $5$ damage to the monster $1$ ;
- the monster $1$ dies, since it received $5$ damage and its defense is $4$ ;
- the monster $4$ does not die, since it received $3$ damage and its defense is $18$ .
During the next three rounds, only the $4$ -th monster is alive, so nothing happens.
During the first round, the following happens:
- the monster $1$ deals $3$ damage to the monster $2$ ;
- the monster $2$ deals $4$ damage to the monster $1$ and the monster $3$ ;
- the monster $3$ deals $7$ damage to the monster $2$ and the monster $4$ ;
- the monster $4$ deals $5$ damage to the monster $3$ and the monster $5$ ;
- the monster $5$ deals $10$ damage to the monster $4$ ;
- the monster $1$ does not die, since it received $4$ damage and its defense is $4$ ;
- the monster $2$ dies, since it received $10$ damage and its defense is $9$ ;
- the monster $3$ dies, since it received $9$ damage and its defense is $1$ ;
- the monster $4$ does not die, since it received $17$ damage and its defense is $18$ ;
- the monster $5$ dies, since it received $5$ damage and its defense is $1$ .
After the first round, the monsters $1$ and $4$ stay alive.
During the second round, the following happens:
- the monster $1$ deals $3$ damage to the monster $4$ ;
- the monster $4$ deals $5$ damage to the monster $1$ ;
- the monster $1$ dies, since it received $5$ damage and its defense is $4$ ;
- the monster $4$ does not die, since it received $3$ damage and its defense is $18$ .
During the next three rounds, only the $4$ -th monster is alive, so nothing happens.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted