DIFFICULTY:
EASY
PREREQUISITES:
BASIC PROGRAMMING KNOWLEDGE
PROBLEM:
There are n boxes containing 10^9 Rupees each. Now the terrorists will pass a few queries which need to be executed as per their order. A query ‘1’ will order the rescue team to remove ‘X’ amount from all boxes from a specified index ‘left’ to ‘right’. With a query ‘0’, output the maximum of the remaining amount in boxes from specified index ‘left’ to ‘right’. If amount in the box is zero, don’t remove anything from that box
NOTE: Boxes will be numbered starting from 1
EXPLANATION:
The challenge is a very basic question. However, care has to be taken in case of TLE.
Take the input as required by the question. If the query is ‘1’, then remove the given amount from each and every box in the given range i.e from ‘L’ to ‘R’. In case of ‘0’ as query, output the maximum of the boxes from the given range i.e from ‘L’ to ‘R’.
To avoid the problem of TLE in case of large inputs, segment tree can be used.
TIME COMPLEXITY:
If brute-force approach is used, O(n^2)
If Segment tree is used, O(nlogn)