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

Автор GayHawk, 6 лет назад, По-английски

You are given N segments defined by their starting point ai and end point bi. You need to determine the number of points such that at least K segments contain them.
What is the most efficient way to do this task? Thanks in advance.

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

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

You need to take a look this problem on codeforces .

I am sure this will help you.

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

Well there was a task on Codeforces similar to this, but I will describe the idea here: save a vector of points. Starting points are type 1, ending points are type 0. Save into the vector a pair, <position, type>. Now sort the vector based on the positions, and also keep track of the current number of segments. Here the task is now pretty simple, just check our current count with K and add to answer the appropriate values