PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
6 Likes
What is the reason behind “query(x) doesn’t return the sum of the elements having key less then or equal to x and update segment(u,v) with val = k is same as update(u,k),update(v+1,-k)”?
1 Like
Segment trees are usually meant for range queries, but here we are just interested in getting the value of one element.
update(u,k): add k to values for 1 to u
update(v,k): add k to values for 1 to v
So, to add k to range (u,v), you have to do update(u,k); update(v+1,-k).
still don’t get it…how do we add k from u to v…any hints
can anybody elaborate the explanation
it’s hard to get the logic behind it
There is problem with the formatting of test cases…
@rsj1308 - In this question , suppose we want to update range [2 4] with value 1, thus first we call update(2) which will update node 2,node 4 and node 8(lets say length of bit array is 10) with value 1. Now call update (5) and this will update node 5, node 6 and node 8 but with -1. Now doing a point query will back trace all the node and the nodes which were not within the range get updated with negative number and that within the range gets updated with positive number. Once you back trace these will cancel out and gives you the correct result.
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 1 0 0 - Update(2,1) - update node 2 -> node 4 -> node 8
0 0 1 0 1 -1 -1 0 0 0 0 - Update(4+1,-1) - update node 5 -> node 6 -> node 8
get (6) -> node 6 + node 4 + node 0 = -1 + 1 + 0 = 0 which proves the above algorithm holds true.
I used lazy propagation and I tested my program with many test cases i got correct ans but whenever I submit I got Wrong answer.
Can anyone tell me what is wrong in my code
https://www.codechef.com/viewsolution/8684827
Why does this solution give TLE? The logic is in accordance of Range Update, Point Query of a BIT.
https://www.codechef.com/viewsolution/10616122
Whereas when I tried the method of “fast input” (borrowed from someone else’s solution) it worked out perfectly fine.
https://www.codechef.com/viewsolution/10616164
Why is that?
Its absolutely non-sense that this question can’t get AC without fast input output. Even with printf scanf and correct efficient algo it gets TLE’d and with fast input it gets AC.
2 Likes
Worst question on codechef.
Without fast input this problem can’t be solved
Is TL of this problem still fixed?
1 Like
Good Question!! 