[Solved] COMP6651: Programming Assignment 2

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 10⁷

1 M 2 10⁵

1 p q N

0 r 10⁹

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.