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 :))