help in LR queries !

can any one explain y im getting WA ?

code : https://www.codechef.com/viewsolution/16384002

mate you are almost correct but one thing you are missing, you are erasing the correct element(at time of updating) but while inserting you simply do ‘v.push_back(val)’. this is wrong as it does guarantee that the vector is still sorted! so, instead of this you should find the correct position of val and then insert it at that position! You are using vector and doing this in vector atleast take O(N) time which didn’t pass whole subtasks! instead you can use multisets(similar to set instead of fact that it can hold multiple similar elements) to speed up this to O(logN) and done :slight_smile:

you are just finding the minimum lower element than val but you have to find the element which has minimum absolute difference. So, it can be greater than the current element(found by lower bound). so, you have to check that also and one last thing you are considering only (a[l] + a[r])/2 as the value of ‘val’ but in case that sum is odd you have to check for the other index also i.e. (a[l] + a[r] + 1)/2.

Hope it helps! if you still have doubts feel free to ask.

i didnt get u !

@msd_007 i have updated my answer. If you still didn’t get feel free to ask again :slight_smile:

@pk301 can you tell me why my solution https://www.codechef.com/viewsolution/16377252 is giving WA in subtask #2 and AC in subtasks #1 and #3.

bro…whenever im doing a query operation im also sorting that vector,present in dat node!

sorry i didn’t see that !

one thing here : “update(0,n-1,l,0,a[l],r);”

you are using a[l] but you have already updated it so, it doesn’t hold previous value now!

atlast done wid it ! tqq fr ur help @pk301

no problem mate :slight_smile: