The New Restaurant

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®

alt text


Now we have :

N * R * logN - “blue updates”

N * R * logN - “green updates”

so our asymptotic is O(N ** R ** logN)

1 Like

@sanja Can you explain how to compute intersected area with green colored cells?

Why do you have kevinsogo’s avatar’s? o.O

2 Likes

i like this :))