LC 3356. Zero Array Transformation II

https://tools.xxooooxx.org/su/gsxoFYBMP

Tag: Binary Search, Prefix Sum

class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int m = nums.size(), n = queries.size();
        int l = 0, r = n + 1;
        while (l < r) {
            int len = (l + r) >> 1;
            vector<int> prefix(m, 0);
            for (int i = 0; i < len; i++) {
                prefix[queries[i][0]] += queries[i][2];
                if (queries[i][1] + 1 < m) prefix[queries[i][1] + 1] -= queries[i][2];
            }
            for (int i = 1; i < m; i++) prefix[i] += prefix[i - 1];
            int mx = INT_MIN;
            for (int i = 0; i < m; i++) mx = max(mx, nums[i] - prefix[i]);
            if (mx <= 0) {
                r = len;
            } else {
                if (len == n) return -1;
                l = len + 1;
            }
        }
        return l;
    }
};