Cover largest set of objects with fixed segments moving constrained

Revision en1, by simiao, 2015-12-13 16:54:56

The problem I'm talking about is this one http://codeforces.net/gym/100733/problem/J, where you have a set of objects and a set of line segments and you want to maximize the number of objects that have at least one segment above and below itself, by just moving the segments horizontally, and the segments and objects never share the same y coordinate (see the problem for a clearer explanation), initially I thought to simulate moving the objects in steps of 1 on x axis so I would try all possible configurations, but once I read that the x and y coordinates may vary from 0 to 10^6, it would be a TLE answer since I can have 10^3 objects, I've seen a problem similar to this one before and couldn't solve, now again. Can someone help me to understand how to get a AC answer on this kind of problem?

Thanks!!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English simiao 2015-12-13 16:54:56 881 Initial revision (published)