D. Хамгийн их хүрхрээ

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Эмускалдыг орчин үеийн байгалын архитектурын чиг хандлагын дагуу хиймэл хүрхрээний загвар бүтээлгэхээр хөлслөсөн. Орчин үеийн хиймэл хүрхрээ нь өргөн хавтгай хананд залгасан хэд хэдэн хөндлөн хавтангуудаас тогтоно. Ус хананы оройгоос доод үзүүр хүртэл хавтангаас хавтангийн хооронд урсана.

Хана $t$ өндөртэй ба ханан дээр $n$ хавтан байна. Хавтан бүр $l_{i}$ өндрөөс эхэлж $r_{i}$ өндөрт дуусах $h_{i}$ өндөртэй хэвтээ хэсэг байна. $i$-р хавтан нь хавтгай дээрх $(l_{i}, h_{i})$ ба $(r_{i}, h_{i})$ цэгүүдийг холбоно. Хананы оройг $( - 10^{9}, t)$ ба $(10^{9}, t)$ цэгүүдийг холбосон хавтан гэж үзэж болно. Үүнтэй адилаар хананы доод үзүүрийг $( - 10^{9}, 0)$ ба $(10^{9}, 0)$ цэгүүдийг холбосон хавтан гэж үзэж болно.

Хүрхрээ илүү бодитой байхын тулд $i$ хавтангаас $j$ () хавтанруу зөвхөн дараах нөхцлүүд хангагдаж байвал л урсана гэдгийг Эмускалд мэдэж байна:

  1. $max(l_{i}, l_{j}) < min(r_{i}, r_{j})$ (хавтангуудын хэвтээ проекцын давхцал);
  2. $h_{j} < h_{i}$ ($j$ хавтан $i$ хавтангийн доор байх);
  3. $(i, k)$ ба $(k, j)$ хослолуудын хувьд дээрх хоёр нөхцөл биелэх $k$ $(h_{j} < h_{k} < h_{i})$ хавтан байхгүй байх.

Ингээд урсгал $min(r_{i}, r_{j}) - max(l_{i}, l_{j})$-тэй тэнцүү буюу хавтангуудын хэвтээ проекцийн давхцлын урттай тэнцүү.

Эмускалд түүний хүрхрээнд ус дээрээс доош нэг замаар урсана гэж шийдсэн. Хэрвээ ус хавтанруу (хананы доод үзүүрээс бусад) урсахдаа яг нэг доор байгаа хавтанруу үргэлжлэн урсана. Хүрхрээнд урсах усны нийт хэмжээ нь дараалласан хоёр хавтангуудын хэвцээ проекцийн хамгийн бага давхцлаар тодорхойлогдоно. Тодорхой хэлбэл:

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

Агуу хүрхрээ хийхийн тулд Эмускалд усны урсгалыг хамгийн их байлгах ёстой боловч түүнд маш олон хавтан байгаа учир бүтээлээ төлөвлөхөд их хэцүү байна. Доорх зурагт Эмускалдын хүсч буй хүрхрээний жишээг харуулсан байна:

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

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$ ба $t$ ($1 ≤ n ≤ 10^{5}$, $2 ≤ t ≤ 10^{9}$) байх ба дээд болон доод хавтангуудыг хассан нийт хавтангуудын тоо болон хананы өндөр байна. Дараагийн $n$ мөр бүрт зайгаар тусгаарлагдсан гурван бүхэл тоо $h_{i}$, $l_{i}$ ба $r_{i}$ ($0 < h_{i} < t$, $ - 10^{9} ≤ l_{i} < r_{i} ≤ 10^{9}$) байх ба $i$-р хавтангийн өндөр, зүүн болон баруун төгсгөлүүд байна.

Ямар ч хоёр хэсэг давхцахгүй.

Гаралт

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

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5 6
4 1 6
3 2 7
5 9 11
3 10 15
1 13 16
Гаралт
4
Оролт
6 5
4 2 8
3 1 2
2 2 3
2 6 12
1 0 7
1 8 11
Гаралт
2

Тэмдэглэл

Эхний жишээ зурагтай харгалзана.

Сэтгэгдлүүдийг ачааллаж байна...