Feedline Overflow

# Feedline Overflow ## Problem The MOOSACO has N feed bins in a long feedline, each with a specific capacity. Bessie, the head cow, manages Q fill operations throughout the day. Each operation adds grain to a contiguous range of bins. After all operations are complete, count how many bins contain more grain than their capacity (i.e., overflow). ## Input Format - **Line 1:** Two integers N and Q (1 ≤ N, Q ≤ 10^5) - **Line 2:** N space-separated integers representing the capacity of each bin (1 ≤ capacity ≤ 10^6) - **Next Q lines:** Each line contains three integers L, R, and X, meaning add X units of grain to bins L through R inclusive (1 ≤ L ≤ R ≤ N, 1 ≤ X ≤ 10^3) ## Output Format Output a single integer: the number of bins that contain more grain than their capacity. ## Constraints - 1 ≤ N, Q ≤ 10^5 - 1 ≤ Capacity ≤ 10^6 - 1 ≤ X ≤ 10^3 - Note: A bin containing exactly its capacity is **not** an overflow. ## Sample ### Input ``` 5 3 3 5 4 6 2 1 3 2 2 5 3 5 5 1 ``` ### Output ``` 2 ``` ### Explanation We have 5 bins with capacities [3, 5, 4, 6, 2]. After operation 1 (add 2 to bins 1-3): [2, 2, 2, 0, 0] After operation 2 (add 3 to bins 2-5): [2, 5, 5, 3, 3] After operation 3 (add 1 to bins 5-5): [2, 5, 5, 3, 4] Comparing to capacities [3, 5, 4, 6, 2]: - Bin 1: 2 ≤ 3 (no overflow) - Bin 2: 5 ≤ 5 (no overflow, equality is allowed) - Bin 3: 5 > 4 (overflow) - Bin 4: 3 ≤ 6 (no overflow) - Bin 5: 4 > 2 (overflow) Therefore, 2 bins overflow.