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.
Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | -is-this-fft- | 148 |
| 5 | SecondThread | 148 |
| 5 | atcoder_official | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 9 | TheScrasse | 144 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jul/23/2024 00:31:10 (j1).
Desktop version, switch to mobile version.
Supported by
You need to take a look this problem on codeforces .
I am sure this will help you.
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