12iq's blog

2008-2009 ACM-ICPC, NEERC, Southern Subregional Contest
By 12iq, history, 7 years ago, In English

link How to solve B, C? For C i know the solution with 2D-segment tree with lazy propagation, but it looks too scary.

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I don't think its possible to solve C using 2D Segtree with lazy.

Let's think about the area covered by each pizza boy, can you see that it forms exactly a square, rotated 45 degrees?

So, the problem now is to find which points are covered by at least K squares. It can be done using Sweep Line. Rotate the squares, it'll become easier.

If you need more details, just talk to me. I still need to read problem B, I'll dedicate some time to it later.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sweep line... always forget about it. Thank you!

    → Reply