848. Robots That Meet With Health Left Over
n robots sit on a line at distinct positions. Robot i has health hp[i] and a direction:
R moves right, L moves left. All move at the same speed and never stop.
When a right-mover meets a left-mover, the one with MORE health survives and loses exactly 1 health; the other is destroyed. If their healths are equal, both are destroyed. Robots moving the same way never meet.
Print the healths of the surviving robots, in the order of their ORIGINAL INPUT INDEX, separated by
single spaces. Print the word none if nothing survives.
positions 3 5 2 6, healths 10 10 15 12, dirs RLRL -> 14
positions 5 4 3 2 1, healths 2 17 9 15 10, RRRRR -> 2 17 9 15 10
positions 1 2, healths 5 5, RL -> none
In the first row the robot at position 2 (input index 3) has health 15. It destroys the left-mover at 5 and then the one at 6, losing 1 each time, so it finishes on 13... except the collisions happen in order of position, and the correct answer is 14. Work it out; the order matters and is the point of the problem.
## Why the input order is useless
Collisions happen along the LINE, not along the input. Sort the robots by position first, ascending, and keep their original indices, because the output is ordered by index rather than by position.
## The stack, and what it holds
Sweep the sorted line left to right, holding a stack of right-movers that are still alive and still looking for something to hit.
if this robot moves R: push it
if this robot moves L:
while it is alive and the stack is non-empty:
top = the stack top
if hp[top] > hp[cur]: hp[top] -= 1; cur is destroyed
elif hp[top] < hp[cur]: hp[cur] -= 1; pop the top
else: pop the top; both destroyed
if it is still alive, it escapes off the left end
The stack top is the NEAREST surviving right-mover to the left, which is exactly who the arriving left-mover meets first. Everything deeper in the stack is shielded until the top is gone.
## Why this really is a monotonic stack
The stack is monotonic in health, strictly increasing from the top downward. If a weaker right-mover sat below a stronger one, the stronger one could never be reached without the weaker one being destroyed first, and the sweep never puts them in that order because a left-mover clears the top before reaching deeper.
The consequence is the usual one: a popped robot is destroyed or has already spent its collision,
so it never returns, and the inner while costs O(n) in total across the whole sweep.
## What survives
Three groups, and forgetting any of them is the classic bug:
* left-movers that emptied the stack and escaped * right-movers still on the stack at the end * everything, when the whole line moves the same way
Collect all of them, sort by original index, and print their CURRENT healths, not their starting ones.
## Related problems
Problem 168 destroys by size with no health left over, so its survivors need no bookkeeping. The damage and the index ordering are what make this a different question.
## Sizes and widths
Healths reach 10^9 and are only ever decremented by one, so the answers stay in the same range.
Positions reach 10^9 and are only compared. 32 bits is technically enough, but the sort keys are
much easier to reason about at 64 bits.
## Cost
Time O(n log n) for the sort by position, then O(n) for the sweep. Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ position[i] ≤ 10^9`, all distinct - `1 ≤ hp[i] ≤ 10^9` - each direction character is `L` or `R`
Input
The first line contains one integer n.
The second line contains n distinct integers, the positions.
The third line contains n integers, the healths.
The fourth line contains a string of n characters, each L or R, the directions.
Output
Print the remaining healths of the surviving robots on one line, separated by single spaces, ordered by their original input index. If no robot survives, print the single word none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.