Fountain
Time limit1.5sMemory limit512 MB
Each reservoir overflows excess water into the nearest lower reservoir with a strictly larger diameter; answer where a given amount poured into reservoir R ends up.
- Level
Medium6 of 10
- Topics
- Array, Stack, Binary search, Prefix sum
- Solved
- No attempts yet
Problem
A new fountain consists of N circular water reservoirs aligned vertically, numbered from top to bottom with integers starting from 1, as shown below:
Each reservoir has its diameter, its capacity, and a tap that can release any amount of the water inside it. Whenever the water volume exceeds the reservoir's capacity, the excess water pours out of its sides and flows down into the closest reservoir with a strictly larger diameter, or down to the waterways if no such reservoir exists.
You have to answer Q independent queries of the following kind: what is the number of the reservoir where the flow ends if you release Vi liters of water from the tap of the Ri-th reservoir? If the flow ends in the waterways, the answer is 0.
Input
The first line of input contains two integers, N and Q.
The next N lines contain two integers Di and Ci each: the diameter and the capacity of the i-th reservoir.
The next Q lines contain two integers Ri and Vi each.
Output
Print Q lines with one integer each: the answers to the queries in the order they are given.
Constraints
- 2 ≤ N ≤ 10^5
- 1 ≤ Q ≤ 2·10^5
- 1 ≤ Ci ≤ 1000
- 1 ≤ Di, Vi ≤ 10^9
- 1 ≤ Ri ≤ N
Hint
The first two queries are illustrated in the image above.
Since the queries are independent of each other, for the third query the fifth reservoir does not overflow.