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.
Input
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.
Output
Write one number - number of magic balls that Bob can catapult successfully.
Example
Input: 7 3 2 3 5 4 2 1 6 3 5 2 5 4 6 Output: 2
Explanation
Bob can catapult balls numbered 1 and 3.
hide comments
rituraj735:
2020-08-20 19:31:13
Plain basic minimum range query required. 0.05 s using sparse table algorithm |
|
karan_221:
2020-08-07 14:22:06
took me 5 tries look for edge cases |
|
immim:
2020-04-01 13:31:46
Not always (A<B) can be (B < A). |
|
abuhanif:
2020-01-24 16:42:27
between means after A and before B
|
|
Vinod Kollipara:
2019-07-29 05:45:59
is anybody able to submit sparse table based solution in java |
|
fardin_abir:
2019-05-29 05:14:33
Accepted, but how to solve this with binary concept? |
|
vcode11:
2019-05-25 12:13:13
AC in one go using sparse table |
|
shoumikk:
2019-05-23 10:42:11
sparse table - 0.02sec |
|
taponidhi:
2018-09-20 16:03:47
Complexity can be O(n) for precomputation and O(1) for query.Just use NGE(Next Greater Element)(0.02 sec) concept.Its a wonderful problem to apply all ur range solving concepts.Make multiple submissions using different concepts.It gave me wonderful clarity and complexity difference idea. Last edit: 2018-09-20 16:04:32 |
|
m2do:
2018-04-26 10:52:04
1. Sparse Tree = 0.04 secs...
|
Added by: | Krzysztof Lewko |
Date: | 2011-05-25 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |