Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Protik and Hill Climbing

By santo_ruet · Limits 1s, 512 MB

Who doesn't want to save a mother? Like everyone,  Protik was finding a way to earn some money (he has no money right now) so that he can donate. He found an event of hill-climbing which says that the person who will be able to climb to the peak of “Wakanda” hill, will be rewarded with prize money. Protik likes hill-climbing very much and he is on a vacation too. So Protik decided to participate and donate the money which he might get from that event.

The hill is a steep hill and there are NN rocks (numbered from 11 to NN) and to climb to the peak of the hill Protik has to use some or all of those rocks. The heights of all the rocks from the ground are given. The rocks with maximum height among them are at the peak of the hill which means Protik has to reach any of the rocks with maximum height. Protik can grab any rock if the difference between that rock’s height and Protik’s height from the ground is at most MM and he will always climb upwards. Protik has an initial weight of WW kg. Each rock has a maximum weight capacity that it can hold which means if Protik’s weight is greater than the rock’s weight capacity, then he can not use that rock to climb. Each rock also has a magical power bib_i. After reaching ithi^{th} (1iN)(1\leq i \leq N) rock, his weight will become max(1,Wbi)max(1, W-b_i), (bib_i can be both negative and positive integer) and he will continue with this weight. After this weight change, if his weight becomes greater than that rock’s weight capacity, he will still be able to stay on that rock. Initially, Protik is on the ground and when he is on any rock, the rock’s height from the ground will be his height from the ground.

Protik doesn't have much time. He needs to be sure that he can climb to the peak of the hill otherwise he will need to find another way of earning some money. So he needs your help because you are a good programmer. You have to tell him whether he can climb to the peak of the hill or not.


The first line of the input consists an integer T(1T104)T (1 \leq T \leq 10^4), the number of test cases.

First line of each test case contains 33 space separated integers NN, MM and WW (1N106,1M,W109)(1 \leq N \leq 10^6 , 1 \leq M , W\leq 10^9 ).

The next 33 lines contains NN space separated integers.

  1. h1h2hN(1hi109)h_1 \leq h_2 \leq \dots \leq h_N (1 \leq h_i \leq 10^9), height of each rock from ground.

  2. a1,a2,,aN(0ai109)a_1, a_2, \dots , a_N (0 \leq a_i \leq 10^9), maximum weight capacity of each rock.

  3. b1,b2,,bN(109bi109)b_1, b_2, \dots, b_N (-10^9 \leq b_i \leq 10^9), magical power of each rock.

It is guaranteed that sum of NN over all test cases will not exceed 10610^6.


Print YES if Protik can win the event otherwise print NO. You can print YES /NO in any case. For example, "Yes", "yes", "YES", etc are equivalent.


3 5 10
3 6 10
12 10 5
3 2 1
4 5 10
3 8 13 17
5 5 4 3
-5 2 -2 2




    0% Solution Ratio


    Login to submit