eddycael's blog

NKMARS spoj — Help!
By eddycael, history, 9 years ago, In English

Hi. I tried to solve this problem: NKMARS . My aproach is: Use sweepline algorithm, sort the events in opening vertical segments and closing vertical segments. Then for each value of X, add the current area to the answer and update the current 'window' of active segments in Y coordinate(from the left to the right). I think that a Segment Tree with lazy propagation must be useful here. But I dont know what data I would save for a single node in the Segment Tree. Can anyone help me? thanks in advance (Sorry for my poor english).

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can do it without lazy propagation, and it's simpler that way.

    Try these two values:
    cover = the number of times the interval (belonging to the node) is fully covered (by a segment), and
    len_covered = how much of the interval is covered.

    So if cover != 0, len_covered will be equal to the length of the interval. Otherwise it will be equal to the sum of len_covered for the two children.

    There's really no benefit in propagating the cover value.

    This way len_covered of the root node gives you the length of the intersection of the sweep line with the set of rectangles.

    Also you could try changing "for each value of X" with "for each interesting value of X" (meaning only the x coordinates of the vertical segments), so your complexity doesn't contain maximum coordinate factors. It's not important for this problem as the coordinates are small, but it's not hard and it's nicer in my opinion.

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

      I will try to solve this problem with your approach. Thanks for your answer... :D

      → Reply