To'g'ri chiziqni bo'yash

Son o'qida $n$ ta kesma bo'yaldi, $i$-kesma $[L_i, R_i]$. Kesmalar bir-birini kesishi yoki ichma-ich bo'lishi mumkin. O'qning bo'yalgan qismi uzunligini toping.

Birinchi qatorda $n$ ($1 \le n \le 10^5$). Keyingi $n$ ta qatorda $L_i$ va $R_i$ ($-2 \cdot 10^9 \le L_i \le R_i \le 2 \cdot 10^9$).

Bitta son — bo'yalgan qism uzunligi.

Kesmalarni chap uchi bo'yicha saralang va ketma-ket yuring, joriy birlashma $[l, r]$ ni saqlab. Keyingi kesma $L_i \le r$ bo'lsa, u joriy birlashmaga qo'shiladi: $r = \max(r, R_i)$. Aks holda joriy birlashma uzunligi $r - l$ javobga qo'shiladi va yangisi boshlanadi.

Nuqta-kesma $[10, 10]$ uzunligi $0$. Javob $4 \cdot 10^9$ gacha yetadi va 32 bitli int ga sig'maydi.

Manba: acmp.ru, 377-masala.