rr459595's blog

By rr459595, history, 5 days ago, In English,

I am getting TLE in this problem. I used lazy propagation with co-ordinate compression.

Link of the problem:- http://www.spoj.com/problems/POSTERS/

Code:- https://pastebin.com/cy0Zvx0Q

How do I apply co-ordinate compression here ?

If points (1,4), (2,6), (8,10), (3,4), (7,10). If I sort it and stor the indices in hashmap, then (1,2,3,4,6,7,8,10) will be compressed to (1,2,3,4,5,6,7,8).If I compress it this way then it fails for this test case.


1 3

4 6

6 7

8 1

1 2

3 4

I get answer as 4 because poster 2 at point (5,5) is not stored here as we have no index for 5.

I am newbie to this topic. Any help would be appreciated.


5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rr459595 (previous revision, new revision, compare).

4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For every poster (l, r), you should also add r + 1 to the compression map, for those cases where there's a visible portion of a poster between other posters.