Berserk Monsters
Contest: Educational Codeforces Round 161 (Rated for Div. 2)
Difficulty rating: 1900
Tags: brute force, data structures, dsu, implementation, math

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
3 1 0 0 0 
0 0 
1 1 1 0

Editorial:
It is important to note that if during the $$$j$$$-th round the $$$i$$$-th monster did not die and none of its alive neighbors died, then there is no point in checking this monster in the $$$(j+1)$$$-th round. Therefore, we can solve the problem as follows: let's maintain a list of candidates (those who can die) for the current round; if the monster dies in the current round, then add its neighbors to the list of candidates for the next round.
Since killing a monster adds no more than $$$2$$$ candidates, the total size of the candidate lists for all rounds does not exceed $$$3n$$$ (since the size of the list for the first round is equal to $$$n$$$ plus no more than $$$2$$$ for each killed monster). Therefore, we can simply iterate through these lists to check if the monster will be killed.
The only problem left is finding the alive neighbors of the monster (to check whether he is killed or not during the round). This can be done by creating an ordered set with the indices of the monsters. set allows us to remove the killed ones and find neighboring monsters in $$$O(\log{n})$$$.
Thus, the solution works in $$$O(n\log{n})$$$.