Given an array of n elements. ‘k’ operations need to be performed on the array.

For each operation start_index, end_index,trim_value is given. One has to trim the value starting from the start_index to end_index inclusive.

If the value at that index is more than or equal to trim value then make it equal to trim_value else leave it as it is. for each A[i] for i between start and end , A[i] = min(A[i],h) .

After performing, ‘k’ such operations find the maximum value of the array.

I have a solution of O(n + k*log(n)). I think it can be optimized to O( n*log(n) ) at least, if not better.

Note: Please try not to use Segment tree or BIT.

Constraints -> n<=10^6 (sure) , A[i] <= 10^6 (Not quite sure of this though)

For Eg. Given array = 7, 2, 8, 5, 1, 6, 4 and k = 3

Following are the k operation (start, end, value) -

1 3 4 => Now the array = 4, 2, 4, 5, 1, 6, 4

3 5 5 => Now the array = 4, 2, 4, 5, 1, 6, 4

4 7 4 => Now the array = 4, 2, 4, 4, 1, 4, 4

So the Maximum value is 4 in the array.