PUMPING WATER | How to solve this problem by using the concept of Segment Tree

general
,
1

Problem Link- https://www.codechef.com/COOK99B/problems/PUMPWAT/

Many people have solved it by using the segment tree. Please tell how to solve this problem by using the concept of Segment Tree ?

2

Hello , I’ll try to explain explain my approach :

First of all let’s see how to solve the actual problem. it’s always optimal to flow the water from the hill with maximum height( heights are distinct ).So , for any interval we can find the maximum height of hill.If it’s position is at the start or at the end of the interval then , it can water all other hills , so this interval is done.Otherwise , we need to decide which part( left or right ) we will water & solve the same problem in other interval just the same way.This can be done recursively.

So , we need to find the maximum height of hill in a range fast enough , for that we can use Segment Tree or Sparse Table which supports range maximum query.I preferred Sparse Table over Segment Tree because the array values are fixed & there is no update operation.
Link to my submission : https://www.codechef.com/viewsolution/21126943
Hope it helps you.Thnx for reading.