It can be observed that the queries can be divided in two categories. Those smaller than sqrt(n)(square root of n) and those bigger.
For the queries bigger than sqrt(n) the solution is simple. Go through the segments of 0's with length > sqrt(n) and calculate how many gas stations have to be built. The formula is length / capacity for full segments between A and B and almost identical for the suffix after A and prefix before B. The complexity for a query is O(sqrt(n)) because you can't have more segments of this type.
For queries smaller than sqrt(n) the formula is the same, but we have too many segments, so we have to do preprocessing to answer fast.
We can build an array L where L[i] = the length of i'th segment of 0's and Sum where Sum[i][j] = sum(L[x] / j) with x <= i and j <= sqrt(n). The preprocessing takes O(n*sqrt(n)). After these computations, we can see that for a query we need the range of full segments of 0's between A and B, this is also a simple precomputation. The query can be now answered in O(1) .
!Also the memory can be optimised from O(n*sqrt(n)) to O(n) by sorting the queries increasingly by capacity. But this wasn't a requirement for full score.
