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
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
i guess my code is fine but it is giving runtime error ,:-(
when blue.mary got wa , its the test cases , not him XD
Sabbir ,could you please tell me where i am getting wrong ? is there any problem in my algorithm or my approach.
use long long that cost me 1 WA but an easy one:-)
O(n*log(n) + q*log(n)) is an accepted solution :)
Akshay Venkataramani, your query function is not running in log(n)