problem is easy…and link is …
and my solution link is
https://www.codechef.com/viewsolution/32032899
AND I FOLLOWED THE FREQUENCY ARRAY APPROACH…JUST CHECK ONCE…AND WHY IT GIVING TLE…MY CODE ALSO RUNS IN LINEAR TIME COMPLEXITY ONLY…ANYONE CAN HELP PLZZ…
Obviously it will timeout. As the complexity of your solution is O(n*m) in the worst case, Which can never pass if n and m are greater than 1000.
Suggestion:
Use some structure for range update and sum query in O(logn) per query. So total complexity will be O(m*logn).
Here Fenwick Tree will do the work easily.
i dont know fenwick tree bro…anyother alternatives exists???
When it comes to update and query then Fenwick Tree is the easiest structure I think.
You can follow this Fenwick Tree blog.
For this problem range update will be the same as an update in difference array suppose you have to add k in range (u,v ) then you have to call add(u-1, k) and add(v,-k).
ok.thank you bro…
Your solution is O(n*m), which will clearly give a TLE. Also, your array declaration is very slow (which is also using an unnecessary loop to initialize array values).