please give editorial or approach for https://www.codechef.com/SEPT16/problems/CIRCLEQ.
thank you.
Main ideas : “sweep line” , BIT
Well known trick reduce SUM on rectangle to “sweep line” + SUM on segment
So now we have O(N ** logN ** R^2) solution ( 50p )
Lets draw some circles.
At picture below we can clearly see that all blue colored cells are fully covered.
As we can see this blue-colored cells form continuous segments.
And we don’t need to modify them one by one , cuz we can modify on segments ( BIT with range updates )
What about green ones???
Let’s try to figure out count of “green colored” cells.
Count of “green cells” is O(perimeter of the circle) , or O®
Now we have :
N * R * logN - “blue updates”
N * R * logN - “green updates”
so our asymptotic is O(N ** R ** logN)
1 Like
Why do you have kevinsogo’s avatar’s? o.O
2 Likes
i like this :))