Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя simiao

Автор simiao, история, 9 лет назад, По-английски

The problem I'm talking about is this one http://codeforces.com/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!!

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Isn't this related somehow to Line Sweep?