SGIFT - Sabbir and gifts
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 n 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
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
Good problem. Solved using multiset and prefix sum.
Did it using coordinate compression nd prefix array.
Did anyone solve using Fenwick Tree? I am getting WA for few cases
Nice problem @sabbir vai
Prefix sum + binary search! : )
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?
Time limit is too strict for JAVA .
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.
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 problemsLast edit: 2017-09-11 15:46:33
thanx a ton buddy @vengatesh15