<p>You have <code>n</code> robots. You are given two <strong>0-indexed</strong> integer arrays, <code>chargeTimes</code> and <code>runningCosts</code>, both of length <code>n</code>. The <code>i<sup>th</sup></code> robot costs <code>chargeTimes[i]</code> units to charge and costs <code>runningCosts[i]</code> units to run. You are also given an integer <code>budget</code>.</p>

<p>The <strong>total cost</strong> of running <code>k</code> chosen robots is equal to <code>max(chargeTimes) + k * sum(runningCosts)</code>, where <code>max(chargeTimes)</code> is the largest charge cost among the <code>k</code> robots and <code>sum(runningCosts)</code> is the sum of running costs among the <code>k</code> robots.</p>

<p>Return<em> the <strong>maximum</strong> number of <strong>consecutive</strong> robots you can run such that the total cost <strong>does not</strong> exceed </em><code>budget</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
It is possible to run all individual and consecutive pairs of robots within budget.
To obtain answer 3, consider the first 3 robots. The total cost will be max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 which is less than 25.
It can be shown that it is not possible to run more than 3 consecutive robots within budget, so we return 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
<strong>Output:</strong> 0
<strong>Explanation:</strong> No robot can be run that does not exceed the budget, so we return 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>chargeTimes.length == runningCosts.length == n</code></li>
	<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= chargeTimes[i], runningCosts[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= budget &lt;= 10<sup>15</sup></code></li>
</ul>

class SegmentTree:
    def __init__(self, data: list[int] | tuple[int]):
        self.length = len(data)
        self.tree = [0] * (2 * self.length)
        self._build(data)

    def _build(self, data: list[int] | tuple[int]):
        for i in range(self.length):
            self.tree[self.length + i] = data[i]
        
        for i in range(self.length - 1, 0, -1):
            self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])

    def find_range_max(self, left_idx: int, right_idx: int):
        # Get max value in interval [left_idx, right_idx).
        range_max = float('-inf')

        left_idx += self.length
        right_idx += self.length
        while left_idx < right_idx:
            if left_idx % 2 == 1:
                range_max = max(range_max, self.tree[left_idx])
                left_idx += 1
            
            if right_idx % 2 == 1:
                right_idx -= 1
                range_max = max(range_max, self.tree[right_idx])
            
            left_idx //= 2
            right_idx //= 2
        
        return range_max


class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        # Base case: only 1st robot.
        max_len = 1 if budget >= chargeTimes[0] + runningCosts[0] else 0
        if len(chargeTimes) == len(runningCosts) == 1:
            return max_len

        cost_prefix_sums = []
        for cost in runningCosts:
            if not cost_prefix_sums:  # 1st cost.
                cost_prefix_sums.append(cost)
                continue
            cost_prefix_sums.append(cost_prefix_sums[-1] + cost)
        
        segment_tree = SegmentTree(chargeTimes)

        queue = []  # (Cost prefix sum end idx) increasing monotonic queue.
        for end_idx, prefix_sum in enumerate(cost_prefix_sums):
            while queue:
                # Subarrays from (queue[0] + 1)th idx to (end_idx)th idx.
                subarray_max = segment_tree.find_range_max(queue[0] + 1, end_idx + 1)
                if subarray_max + (end_idx - queue[0]) * (prefix_sum - cost_prefix_sums[queue[0]]) <= budget:
                    break
                
                # If a start idx & current end idx exceed budget, so will a bigger end idx with this start idx.
                queue.pop(0)

            if queue:
                if end_idx - queue[0] > max_len:  # Check the longest subarray in queue.
                    max_len = end_idx - queue[0]

                if queue[0] == 0:  # Also check subarray from 0th idx to (end_idx)th idx.
                    subarray_max = max(chargeTimes[queue[0]], chargeTimes[0])
                    if subarray_max + (end_idx + 1) * prefix_sum <= budget:
                        max_len = end_idx + 1

            queue.append(end_idx)

        return max_len

1935