Кино фестивалийн хүсэлтүүд

2s

512MB

1538

0%

Range Queries

Кино фестивальд $n$ кино үзүүлнэ. Кино бүрийн эхлэх болон дуусах цаг мэдэгдэнэ.

Дараах хэлбэрийн $q$ хүсэлтүүдийг боловсруулна: фестивальд тодорхой цагт ирж, тодорхой цагт явбал хамгийн ихдээ хэдэн кино үзэх боломжтой вэ?

Хоёр кино үзэхийн тулд эхний кино хоёр дахь кино эхлэхээс өмнө эсвэл яг тэр үед дууссан байх ёстой. Ирсэн цагаасаа яг эхний кино эхлүүлж, сүүлийн кино дууссан цагт яг явж болно.

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

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

Эхний мөрөнд $n$ ба $q$ хоёр бүхэл тоо байна: кинонуудын тоо ба хүсэлтүүдийн тоо.

Дараа нь кинонуудыг тодорхойлсон $n$ мөр байна. Мөр бүрт $a$ ба $b$ хоёр бүхэл тоо байна: киноны эхлэх болон дуусах цаг.

Эцэст нь хүсэлтүүдийг тодорхойлсон $q$ мөр байна. Мөр бүрт $a$ ба $b$ хоёр бүхэл тоо байна: ирэх болон явах цаг.

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

Хүсэлт бүрийн хувьд үзэх боломжтой кинонуудын хамгийн их тоог хэвлэ.

Хязгаарлалт

$1 \le n,q \le 2 \cdot 10^5$
$1 \le a < b \le 10^6$

Жишээ

Оролт1

Гаралт1

0
2
1

0.1 / 64 KiB

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