Practice on Toph

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

Dominoes Forever

Limits 1s, 512 MB

Once when I was little, my father took me to a tobacco shop! It is surprising, but true. He asked the shopkeeper to give me some empty packets of cigarettes. The shopkeeper obliged and gave me a lot of empty packets in a bag. I took them back home and my brother showed me how to make domino out of the packets. Since then, domino had become an important part of my pastime.

Here's how you play domino, you place cigarette boxes one after the other. The boxes are placed in such a way that if you drop the first box with your hand, it will touch the second box. As a result, the second box will fall, which will touch the third box. Thus, the third box will fall as well. The process continues until all the boxes are dropped. This process is famously called the domino effect. If you search the YouTube, you will be able to see a plenty of amazing domino videos.

Now placing dominoes one after the other might be very tricky. If a domino XX is placed too far forward from the next one YY, then XX will not be able to touch the domino YY when it falls. As a result, the domino YY and the ones after that will not fall and the game will not end. In this problem, we will use our programming skill to predict the outcome of this beautiful game.

Let us imagine that we have NN dominoes. These dominoes are placed from left to right in sequential order. The 0-th domino is placed at the leftmost position and the N1N-1-th domino is placed at the rightmost position. The ii-th domino is placed at a certain place pi and has a height of hih_i. Now, if we tilt the ii-th domino towards right, it will touch and drop all the dominoes to its right, if they are reached. Formally, the ii-th domino will drop the jj-th domino if the following condition is satisfied:

hi+pi>pj h_i + p_i > p_j and i<ji < j .

If the j'th domino is dropped, it will drop towards right and continue to domino effect as long as possible.

Now you will be given the number of dominoes NN that you have, the position and height of each of the dominoes. You have to answer queries of the following form: if the ii-th domino is dropped towards right, how many dominoes will fall as the result of the domino effect.


The first line contains an integer NN (1N10001 \le N \le 1000), the number of domino pieces available. The next line contains NN integers hih_i (1hi1091 \le h_i \le 10^9), the the height of each of the dominoes in sequential order. The next line contains NN integers pip_i (1pi2×1091 \le p_i \le 2 \times 10_9), the position of the dominos in sequential order. You can safely assume that the positions will be given in increasing order.

The next line contains an integer MM (1M1061 \le M \le 10_6), the number of queries to perform. The following MM lines will contain one integer qiq_i (1qiN1 \le q_i \le N), the index of the domino that we want to tilt.


For each query, output an integer, the number of dominoes that will fall if the qiq_i-th domino is tilted.


5 3 1
1 3 5



72% Solution Ratio

salahuddinEarliest, Dec '16

NaimulFastest, 0.1s

salahuddinLightest, 3.9 MB

jaberndcShortest, 429B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.