SGIFT - Sabbir and gifts

no tags 

Sabbir is a little boy. he went to a gift shop with his mother. there were n different types of gifts in the shop . all gifts were attractive to sabbir. he wanted to buy all the gifts which are in price range    . you are given prices of all the gifts and  a b . sabbir's mother need your help.  please calculate the total amount of price of all gifts of that range for sabbir's mother. 


in the first line there will be n . number of gifts in the shop.
in the next line there will be integers p1, p2 , p3 ... pn   denoting price of every gift

in the 3rd line there will be Q number of queries.

next Q lines contain two integes a and b


print Q lines . every line contains one integer , sum of all prices for that range given in the query.


1 3 2 1 5 2 2
1 2
1 5
3 5
4 5 Output: 8

NOTE: for first query sabbir will buy all the gifts of prices 1 , 2 , 1 , 2, 2 . so, sum is 8
for second query sabbir will buy all the gifts . so the sum is 16

hide comments
fahad991: 2020-08-16 16:37:55

Good problem. Solved using multiset and prefix sum.

an09mous: 2020-02-18 18:41:11

Did it using coordinate compression nd prefix array.

dilip23: 2019-05-28 16:03:39

Did anyone solve using Fenwick Tree? I am getting WA for few cases

limon_88: 2019-04-28 21:01:22

Nice problem @sabbir vai

eulerkochy: 2018-12-13 19:01:21

Prefix sum + binary search! : )

rifazn: 2018-01-26 16:54:08

I sorted using python's built in sort method that sorts in O(n logn), then I used binary search for finding the lower bound, then again for finding the upper bound. Doing a sum(lower-bound, upper-bound) makes the whole solution into O(n) which is maybe why I am getting a TLE. Is that what I am not doing right here? How can I do the sum in less than O(n) in this case?

abhi1004: 2017-12-11 20:10:37

Time limit is too strict for JAVA .
Complexity of my algorithm is (O(q*log(n))) still giving TLE.

nadstratosfer: 2017-10-13 18:18:18

I hardly sympathize with the bloatware called Java but the time limit here does make it a I/O challenge. O((n+q)*logn) in Python TLEs unless the code looks like a golfing solution. This shouldn't be necessary for AC.

testing java: 2017-09-11 15:13:07

What's the point of so strict time limit? I try to solve it in java, and because of time limits I do not know whether there is something wrong with algorithmic part of my code or I got TLE simply because my io isn't fast enough. It slightly spoils fun from solving problems

Last edit: 2017-09-11 15:46:33
holmesherlock: 2017-05-27 13:24:20

thanx a ton buddy @vengatesh15

Added by:sabbir
Time limit:0.400s-0.800s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)