Өрөө хуваарилах

2s

512MB

1185

0%

Sorting and Searching

Том зочид буудалд удахгүй $n$ үйлчлүүлэгч ирнэ. Үйлчлүүлэгч бүр нэг өрөө хүснэ.

Үйлчлүүлэгч бүрийн ирэх, гарах өдөр мэдэгдэж байна. Эхний үйлчлүүлэгчийн гарах өдөр хоёрдугаар үйлчлүүлэгчийн ирэх өдрөөс өмнө байвал хоёр үйлчлүүлэгч нэг өрөөнд бууж болно.

Бүх үйлчлүүлэгчид зориулж шаардагдах өрөөний хамгийн бага тоог болон өрөө хуваарилалтыг ол.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд $n$ бүхэл тоо байна: үйлчлүүлэгчдийн тоо.

Дараа нь $n$ мөр байна, мөр бүр нэг үйлчлүүлэгчийг тодорхойлно. Мөр бүрт хоёр бүхэл тоо $a$ ба $b$ байна: ирэх болон гарах өдөр.

Гаралтын формат

Эхлээд $k$ бүхэл тоог хэвлэ: шаардагдах өрөөний хамгийн бага тоо.

Дараа нь оролтын дарааллаар үйлчлүүлэгч бүрийн өрөөний дугаарыг агуулсан мөр хэвлэ. Өрөөнүүд $1,2,\ldots,k$ гэж дугаарлагдсан. Ямар ч хүчинтэй хариулт зөвшөөрөгдөнө.

Хязгаарлалт

$1 \le n \le 2 \cdot 10^5$
$1 \le a \le b \le 10^9$

Жишээ

Оролт1

Гаралт1

2
1 2 1

0.1 / 64 KiB

Редактор уншиж байна...