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.