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.
