Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
D. K-сегментийн огтлолцол
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд координатын $Ox$ тэнхлэг дээр орших $n$ ширхэг сегмент болон $k$ тоо өгөгдөв.Хэрэв ямар нэг цэг нь дор хаяж $k$ ширхэг сегментэд харьяалагдаж байвал тус цэгийг ханасан гэж үзнэ.Тэгвэл бүх ханасан цэгүүдийг агуулах бөгөөд өөр бусдын агуулаагүй $Ox$ тэнхлэг дээрх хамгийн жижиг(сегментийн тоогоороо) сегментүүдийн олонлогийг олно уу.
Оролт
Эхний мөрөнд сегментийн тоо болон $k$-ын утгыг илэрхийлэх 2 бүхэл тоо $n$ болон $k$ ($1 ≤ k ≤ n ≤ 10^{6}$) өгөгдөнө.
Дараагийн $n$ ширхэг мөрний мөр болгонд $i$-дахь сегментийн захын цэгүүдийг илэрхийлэх 2 бүхэл тоо $l_{i}, r_{i}$ ($ - 10^{9} ≤ l_{i} ≤ r_{i} ≤ 10^{9}$) өгөгдөнө.Сегментүүд нь эмх замбараагүй өгөгдөх ба хоорондоо огтлолцсон байж болно.Мөн сегментүүд нь дурын дарааллаар өгөгдөнө.
Гаралт
Эхний мөрөнд сегментүүдийнх нь хамгийн бага тоо(өөрөөр хэлбэл сегментүүдийн олонлогийн элементийн тоо)болох $m$ бүхэл тоог хэвлэнэ.
Дараагийн $m$ ширхэг мөрний мөр болгонд хариулт болох сегментүүдийн олонлогийн $j$-дэх сегментийн захын цэгүүд болох 2 бүхэл тоо $a_{j}, b_{j}$ ($a_{j} ≤ b_{j}$)-г хэвлэнэ.Сегментүүд нь зүүнээс баруун уруугаа бичигдсэн байна.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
3 2 0 5 -3 2 3 8
Гаралт
2 0 2 3 5
Оролт
3 2 0 5 -3 3 3 8
Гаралт
1 0 5