can any one explain y im getting WA ?
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
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
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