Killer Monsters

★★★★★

3.8

9 votes

Stacks, Basics of Stacks, Sets, Data Structures

Details

Problem

Given an array $monsters$ denoting strengths of $N$ monsters, we start with an empty battlefield, at each minute $i$ , the $i^{th}$ monster joins the battlefield and kills all monsters whose strength is less than or equal to his strength.

Find the number of monsters alive in the battlefield at end of $i^{th}$ minute for each $0 \le i < N$ .

NOTE:

Use of Fast I/O is recommended for this problem.
$i^{th}$ monster becomes part of the battlefield at the end of killing spree.

Input Format:

First line contains an integer $T$ , the number of test cases.
First line of each testcase contains an integer $N$ , the number of monsters..
Second line of each testcase contains $N$ space seperated integers, the strengths of $N$ .monsters.

Output Format:

For each testcase, output $N$ integers denoting the number of monsters alive after $i^{th}$ minute for each $0 \le i < N$ .

Constraints:

$1 \le T \le10$
$1 \le N \le 5 \times 10^5$
$0 \le monsters[i] \le 10^4$

Sample Input

3
5
3 0 3 4 1
5
5 4 3 2 1
7
1 2 3 3 4 4 0

Sample Output

1 2 1 1 2
1 2 3 4 5
1 1 1 1 1 1 2

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

In the First Test Case, the strengths of monsters are $[3, 0, 3, 4, 1]$
- At $0^{th}$ minute, the first monster joins the battlefield. There are no monsters already on the battlefield. After $0^{th}$ minute, the alive monsters are $[3]$ .
- At $1^{st}$ minute, the second monster joins the battlefield. The alive monsters are $[3]$ , but no one's strength is less than or equal to $0$ , no one gets killed and $0$ becomes part of battlefield, The alive monsters now are $[3, 0]$ .
- At $2^{nd}$ minute, the third monster joins the battlefield. The alive monsters are $[3, 0]$ , and the strength of the third monster is $3$ , which is equal to the strength of the first and greater than the strength of the second monster, Thus both get killed, and only current monster remains, The alive monsters remain $[3]$ .
- At $3^{rd}$ minute, the fourth monster joins the battlefield. The active monsters are $[3]$ , and the strength of the fourth monster is $4$ , which is greater than the strength of currently alive monster, thus it gets killed, The alive monsters remain $[4]$ .
- At $4^{th}$ minute, the fifth monster joins the battlefield. The active monsters are $[4]$ , and the strength of the fifth monster is $1$ which is less than the strength of currently alive monsters, so it kills no one and becomes part of battlefield. The alive monsters now are $[4, 1]$ .
In the Second Test Case, the strengths of monsters are $[5, 4, 3, 2, 1]$
- At $0^{th}$ minute, the first monster joins the battlefield. There are no monsters already on the battlefield. After $0^{th}$ minute, the alive monsters are $[5]$ .
- At $1^{st}$ minute, the second monster joins the battlefield. The alive monsters are $[5, 4]$ .
- At $2^{nd}$ minute, the third monster joins the battlefield. The alive monsters are $[5, 4, 3]$ .
- At $3^{rd}$ minute, the fourth monster joins the battlefield. The alive monsters are $[5, 4, 3, 2]$ .
- At $4^{th}$ minute, the fifth monster joins the battlefield. The alive monsters are $[5, 4, 3, 2, 1]$ .

Contributers:

Abhishek Choudhary

Madhumeeta Bauk