Nuqtalar va kesmalar

Son o'qida $n$ ta kesma va $m$ ta nuqta berilgan. Har bir nuqta nechta kesmaga tegishli ekanini toping. Uchlari $a$ va $b$ bo'lgan kesmaga $\min(a, b) \le x \le \max(a, b)$ bo'lgan $x$ nuqta tegishli.

Birinchi qatorda $n$ va $m$ ($1 \le n, m \le 10^5$). Keyingi $n$ ta qatorda $a_i$ va $b_i$ — kesma uchlari (istalgan tartibda). Oxirgi qatorda $m$ ta butun son — nuqtalar. Barcha sonlar moduli $10^9$ dan oshmaydi.

Bitta qatorda $m$ ta son — har bir nuqta uchun, kirishdagi tartibda.

Har bir juftlikni tekshirish $O(nm)$ — $10^{10}$ amal. $x$ ni o'z ichiga oluvchi kesmalar soni = (chap uchi $\le x$ bo'lgan kesmalar) − (o'ng uchi $< x$ bo'lgan kesmalar). Chap va o'ng uchlarni alohida saralang va har bir nuqta uchun ikkala sanoqni binar qidiruv bilan toping: $O((n + m) \log n)$.

Kesma uchlari teskari berilishi mumkin ($5\ 1$) — avval ularni tartiblang. Kesma uchidagi nuqta ham kesmaga tegishli.

Manba: acmp.ru, 396-masala.