I am getting WA for this solution. Please tell me what is wrong with this solution.
Check this test-case
4
7 8 6 4
4
3 3
2 2
3 8
3 10
The answer should be 0,2,4,0
But my code was giving 0,2,0,0
so I corrected it.
Now it is giving 0,2,4,0
But still getting WA on submission.
Updated code
No, the correct answer should be
0
0
4
0
Your output is still wrong.
I think I misunderstood the question statement. Do we start again from 1st index after every query?
Do we start again from 1st index after every query?
No we start from city X corresponding to each query.
1 Like
So if x < current position after the previous query then we move back to x. Is it correct?
There’s no notion current index in this problem. In each query K people are dropped at index X and all those K people keep on moving to right until all of them settle to some index.
@cubefreak777 I corrected it and now it is giving 0,0,4,0. But on submission it gives TLE. Any suggestions on how I can optimize it?
updated code
Complexity of your code is \mathcal{O(N\times Q)} which is too slow for this problem. Replace the vector with a set instead. And erase the positions which reach their max capacity. Size of set will keep on reducing the hence amortized complexity would be good enough to pass.
1 Like
yahh
Hello I have one small doubt. If we keep removing the cities which reach 0, then how will we calculate the distance which is travelled because of them. Because if a city has 0 capacity. still people will have to proceed further and that should be added to the overall distance travelled. Please rectify this doubt I am stuck in TLE from 3-4 days and I don’t want to see the code. i only want a hint
dude overall distance will be calculated based on current situation let’s see
city->1,2,3,4
cap->5,5,6,1
(now the main reason u r getting tle is not using lower_bound)
first we start with 2(x) city we fill it full cap. witch is we take min of (k,cap) and fill it and we update distance D=min(k,cap)*(x-current _city)
and we update cap.like->
city 1,2,3,4;
cap 5 ,0,6,1;
now by using lower_bound we can get next city which we have update also we can delete it
so it look like
city->1,3,4;
cap->5,6,1;
now here’s the deal by using lower_bound(2) u get city(3) .becuz lower_bound return value witch is grater than or equal to it so this we get 3(x) .now just keep repeating it and update your distance,city,cap.
can anyone plz explain the distance fact of this problem I am not understanding