12iq's blog

2008-2009 ACM-ICPC, NEERC, Southern Subregional Contest
By 12iq, history, 9 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

»
9 years ago, hide # |
← 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