THRBL - Catapult that ball

Bob has unusual problem. In Byteland we can find a lot of hills and cities. King of Byteland ordered Bob to deliver magic balls from one city to another. Unfortunately, Bob has to deliver many magic balls, so walking with them would take too much time for him. Bob came up with great idea - catapulting them.

Byteland is divided into intervals. Each interval contains city and hill.

Bob can catapult magic ball accurately from city A to city B, if between them there isn't higher hill than A's hill.


Every test case contains N and M (N <= 50000, M <= 50000), number of intervals and number of balls.

In next line there's N numbers H (H <= 10^9) separated by one space.

In next M lines numbers A and B (1 <= A, B <= N), number of city from which we want to catapult the ball and number of city to which we want to catapult the ball.


Write one number - number of magic balls that Bob can catapult successfully.


7 3
2 3 5 4 2 1 6
3 5
2 5
4 6



Bob can catapult balls numbered 1 and 3.

hide comments
voidpoint11: 2024-05-21 20:54:49

AC using Segment tree. Easy

sxie12: 2022-08-28 02:20:16

We allow B's hill to be higher than A's hill but not any hill between A and B. Kind of hard imagining how that works in practice.

Last edit: 2022-08-28 02:22:31
idkreally: 2022-06-03 22:05:24

AC using Sparse Table (0.05s)

latecomer04: 2022-03-07 14:24:44

straight forward segment tree question.

rushi2001: 2021-05-26 17:10:24

Very Easy Question
Used Sparse table
check if max in range A to B-1 is equal to A
take care of conditions
if A > B , A == B

healthy567: 2021-05-07 09:38:17


cryp_bipul17: 2021-04-27 11:25:28

Be alert handle the cases L<=B as well as B>A too
got 3 WAs for not handling them

omharicu: 2021-04-13 20:51:58

Missing testcases: 'NoneT
what it means?

amantu_amir: 2021-01-08 21:26:14

AC with Sparse Table. You can use Segment Tree or Binary Indexed Tree to solve this problem.

baller_14: 2020-10-27 05:13:07

AC using stack

Added by:Krzysztof Lewko
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64