COMP 6651: Algorithm Design Techniques

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 ≤ 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.

Sale!