Codeforces Round #792 (Div. 1 + Div. 2)
21:45:32 |
Codeforces Round #793 (Div. 2)
3 өдрийн дараа |
Educational Codeforces Round 129 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #794 (Div. 1)
7 өдрийн дараа |
Codeforces Round #794 (Div. 2)
7 өдрийн дараа |
E. Майк ба Геометрийн бодлого
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Майк ОУМО(Олон улсын математикийн олимпиад)-д бэлдэхийг хүссэн боловч тэрээр геометрийн тухай мэдэхгүй байв. Иймд түүний багш түүнд нэгэн сонирхолтой геометрийн бодлого өгчээ. $f([l, r]) = r - l + 1$ гэдгээр $[l, r]$ сегмент дээр байх бүхэл тоон цэгүүдийн тоог тэмдэглэв(энд $l ≤ r$ байх бөгөөд гэж үзнэ). Танд 2 бүхэл тоо $n$ болон $k$ мөн $OX$ тэнхлэг дээрх $n$ ширхэг хаалттай интервал $[l_{i}, r_{i}]$-ууд өгөгдсөн ба та дараах нийлбэрийн утгыг олох юм:
Өөрөөр хэлбэл та эдгээр өгөгдсөн сегментүүдийн аль ч $k$ ширхэг сегментүүдийнх нь огтлолцол дээрх бүхэл тоон цэгүүдийн тоонуудын нийлбэрийг олох юм.
Бодлогын хариулт хэтэрхий том тоо байж болох учраас хариултыг $1000000007$ ($10^{9} + 7$) модулаар бодон хэвлэнэ үү.
Майк уг бодлогыг бодож чадахгүй байгаа тул түүнд таны тусламж хэрэг болжээ. Та түүнд тусална тийм үү?
Оролт
Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1 ≤ k ≤ n ≤ 200 000$) өгөгдөх ба эдгээр нь харгалзан сегментүүдийн тоо болон огтлолцлын хэсэгт байх сегментийн тоог илэрхийлнэ.
Дараа нь $n$ ширхэг мөр өгөгдөх ба эдгээрийн $i$-дахь мөрөнд 2 бүхэл тоо $l_{i}, r_{i}$ $( - 10^{9} ≤ l_{i} ≤ r_{i} ≤ 10^{9})$ өгөгдсөн байх бөгөөд эдгээр нь $i$-р сегментийн доод болон дээд хязгааруудыг илэрхийлнэ.
Гаралт
Майк-ын бодлогын хариултыг $1000000007$ ($10^{9} + 7$) модулаар бодсон утгыг хэвлэнэ үү.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
3 2 1 2 1 3 2 3
Гаралт
5
Оролт
3 3 1 3 1 3 1 3
Гаралт
3
Оролт
3 1 1 2 2 3 3 4
Гаралт
6
Тэмдэглэл
Эхний жишээ:
;
;
.
Иймд хариулт нь $2 + 1 + 2 = 5$ байна.