CocoCat's blog

2257D
By CocoCat, history, 2 weeks ago, In English

Hi everyone! I was just writing to ask if anybody could explain the solution of 2257D to me (I couldn't solve it rip rating) I felt the editorial was way too vague and incomprehensible so I'd appreciate it a lot if anyone can elaborate here. ty :)

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 weeks ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

Because the specifics of my solution are a bit complex, I'll give the idea of how to solve the problem

Even though S is large, the upper bound for the number of factors for S is 2^(log n/ log log n) (thank you srvntofthejudge for the correction!). For every factor, figure out how much area the rectangle X by Y would be when X is equal to the factor, and Y is equal to S/X. However, because of overlaps, you must remove the previous overlaps of smaller factors.

Then, for every query, you use binary search and segment trees to figure out the answer. If you want to know the specifics of how I do it, let me know!

→ Reply
»
2 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

So it's quite simple.

Essentially, try imagining the shape of covered squares. It looks like a staircase where the height of each is 1/(factor) of the original number.

for a rectangle (x, y), any towers in the staircase that go beyond y can be counted via width * height. any towers in the staircase that don't go beyond y can be counted simply via a prefix sum. you can binary search on factors to find this point, making the sqrt S cost of factor inding dominate. it wnds up being O(sqrt S) or to be more accurate O(sqrt S + k log 2^O(log s / log log s))

→ Reply