The New Restaurant

please give editorial or approach for
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

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


i like this :))

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