Description
1 Problem
You are given an array of N elements which are initialized to 0. You are given a sequence of M operations of the sort (p,q,r). The operation (p,q,r) signifies that the integer r should be added to all array elements A[p],A[p + 1],…,A[q]. You are to output the maximum element in the array that would result from performing all M operations. There is a naive solution that simply performs all operations and then returns the maximum value, that takes O(MN) time. We are looking for a more efficient algorithm.
2 Input
The first line will have two integers N and M separated by a space. The next M lines each have 3 integers separated by spaces. The input can be assumed to obey the following constraints:
3 ≤ N ≤ 107
1 ≤ M ≤ 2 ∗ 105
1 ≤ p ≤ q ≤ N
0 ≤ r ≤ 109
3 Output
The output should be a single line containing the required maximum value.
4 Example
Sample Input
6 3
1 3 200 2 5 50
3 6 100
Sample Output
350
Explanation
The array has 6 elements initialized to 0, and there will be 3 operations.
After the first operation, the array would be [200,200,200,0,0,0].
After the second operation, the array would be [200,250,250,50,50,0].
After the third operation, the array would be [200,250,350,150,150,100]. So the required answer is the maximum value in the array, which is 350.
5 Requirements
For the constraints given above, your program should run in 1 second. You must submit source code for a program written in C/C++/Java on the Electronic Assignment System. Some test cases will be provided on the course website. You can verify if your program works on the test cases before submitting.
