Today I tried to solve 1932F - Feed Cats, and finally got Accepted, though not after some hard debugging. You can give a try at the problem first before reading this.
Here is my original submission with WA on test 3 268592520 and here is my AC submission 268597071.
My thought process went like this:
I thought of a segment tree with sweepline style solution
Though using segment tree with n=10^6 is very risky (high constant time)
So I went ahead and compress the coordinates of the start point and end point of each segment.
Query an addition at the compressed start point and a removal at the (compressed end point) +1.
This is WRONG, however. Since there is a chance of nothing happening at the compressed end point and something else happening at the (compressed end point) +1 that might influence the answer, this can give a wrong result. The really important part is the compressed (end point +1) where the removal ACTUALLY happens, which I failed to realise for 90 minutes.
Did I learn my lesson? Yes. Did you waste your time reading something you already know/ don't need to know yet? I hope not. Either way, perhaps I will leave this blog here as a cautionary tale for myself, to better tackle future problems I will have to solve.
why u stucked at blue too long ?
Too long ? : (
You can solve that without a segment tree. Sort segments, calculate prefix sums for starts and ends of segments. For each point, note the smallest start point of a segment that passes through that point. This can be done in linear time after sorting the segments (so nlogn in total).
268648167
That's a very elegant solution! I'm just glad that I came up with my own.
Same