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 stored 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.↵
6 ↵
1 3 ↵
4 6 ↵
6 7 ↵
8 10 ↵
1 2 ↵
3 4 ↵
I get answer as 4 because poster 3 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.
↵
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 stored 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.↵
6 ↵
1 3 ↵
4 6 ↵
6 7 ↵
8 10 ↵
1 2 ↵
3 4 ↵
I get answer as 4 because poster 3 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.
