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 X is placed too far forward from the next one Y, then X will not be able to touch the domino Y when it falls. As a result, the domino Y 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 N dominoes. These dominoes are placed from left to right in sequential order. The 0th domino is placed at the leftmost position and the N-1th domino is placed at the rightmost position. The i’th domino is placed at a certain place pi and has a height of hi. Now, if we tilt the ith domino towards right, it will touch and drop all the dominoes to its right, if they are reached. Formally, the i’th domino will drop the j’th domino if the following condition is satisfied:

hi + pi > pj and i < 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 N that you have, the position and height of each of the dominoes. You have to answer queries of the following form: “if the i’th domino is dropped towards right, how many dominoes will fall as the result of the domino effect”.


The first line contains an integer N ( 1 &le; N &le; 1000 ), the number of domino pieces available. The next line contains N integers hi ( 1 &le; hi &le; 109 ), the the height of each of the dominoes in sequential order. The next line contains N integers pi ( 1 &le; pi &le; 2 * 109 ), 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 M ( 1 &le; M &le; 106 ), the number of queries to perform. The following M lines will contain one integer qi ( 1 &le; qi &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 qi’th domino is tilted.


5 3 1
1 3 5



52% Solution Ratio

oneoff.2CPrSaJpzIEarliest, Dec '16

IstiaqueShubhoFastest, 0.1s

salahuddinLightest, 3.9 MB

jaberndcShortest, 429B


Login to submit