Killer Monsters

Practice

3.7 (10 votes)

Stacks

Basics of stacks

Sets

Data structures

Problem

69% Success 3687 Attempts 20 Points 2s Time Limit 256MB Memory 1024 KB Max Code

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

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]\).

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Submissions

Please login to view your submissions

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Please login to use the editor

Loading...

Code Editor

Results

Please login to use the editor

Loading...

Code Editor

Results