4008. Minimum Initial Strength to Defeat All Monsters

You are given an integer array monsters, where monsters[i] represents the strength of the i^th monster.

You are also given a 2D integer array boosts, where boosts[i] = [l_i, r_i, v_i] indicates that v_i is added to your temporary bonus while fighting any monster whose index lies in [l_i, r_i]. Boost ranges may overlap, and the values of all applicable boosts are added together.

You start with a non-negative initial strength and fight the monsters from left to right.

For each monster at index i:

• Let bonus be the sum of the values of all boosts that apply to monster i.
• You can defeat the monster only if your current strength plus bonus is at least monsters[i].
• After defeating the monster, only your current strength decreases by monsters[i]. If it becomes negative, it is set to 0.

Return the minimum initial strength required to defeat all monsters.

Note: The temporary bonus is used only to determine whether the current monster can be defeated. It does not otherwise change your current strength.

class Solution {
    bool helper(vector<int>& A, vector<long long>& p, long long s) {
        for(int i = 0; i < A.size(); i++) {
            if(A[i] > s + p[i]) return false;
            s = max(0ll, s - A[i]);
        }
        return true;
    }
public:
    long long minInitialStrength(vector<int>& monsters, vector<vector<int>>& boosts) {
        vector<long long> pre(monsters.size() + 1);
        for(auto& b : boosts) {
            pre[b[0]] += b[2];
            pre[b[1] + 1] -= b[2];
        }
        for(int i = 1; i < pre.size(); i++) pre[i] += pre[i-1];
        long long l = 0, r = 1e18, res = r;
        while(l <= r) {
            long long m = l + (r - l) / 2;
            bool ok = helper(monsters, pre, m);
            if(ok) {
                res = m;
                r = m - 1;
            } else l = m + 1;
        }
        return res;
    }
};