Сегментүүдийн ул мөр II

2s

512MB

1720

0%

Geometry

Төгсгөлүүдийн координатууд нь бүхэл тоо болсон $n$ сегмент байна. x-координат бүр $0$ -ээс $m$ хооронд. Сегмент бүрийн налуу бүхэл тоо.

$0,1,\dots,m$ x-координат бүрт ямар нэг сегментэн дээрх хамгийн их цэгийг ол. Ямар нэгэн цэгт сегмент байхгүй бол хамгийн их утга $-1$ .

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

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

Эхний мөрөнд $n$ , $m$ хоёр бүхэл тоо байна: сегментүүдийн тоо ба хамгийн их x-координат.

Дараагийн $n$ мөрөнд сегментүүдийг тодорхойлно. Мөр бүрт $x_1$ , $y_1$ , $x_2$ , $y_2$ дөрвөн бүхэл тоо байна: $(x_1,y_1)$ , $(x_2,y_2)$ цэгүүдийн хооронд сегмент байна.

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

$m+1$ бүхэл тоо хэвлэ: $x=0,1,\dots,m$ үеийн хамгийн их цэгүүд.

Хязгаарлалт

$1 \le n, m \le 10^5$
$0 \le x_1 < x_2 \le m$
$0 \le y_1,y_2 \le 10^9$

Жишээ

Оролт1

Гаралт1

-1 2 8 6 6 7

0.1 / 64 KiB

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