E. Поликарпус ба Даалгаврууд

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

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

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

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

Поликарпус-д маш олон даалгавар өгөгджээ. Даалгавар болгон нь 3-н бүхэл тоо $l_{i}$, $r_{i}$ болон $t_{i}$-аар дүрслэгдэнэ. $(l_{i}, r_{i}, t_{i})$ гэсэн 3-н бүхэл тоо нь та $i$-р даалгаврыг гүйцэтгэхийн тулд нэгэн бүхэл тоо $s_{i}$ $(l_{i} ≤ s_{i}; s_{i} + t_{i} - 1 ≤ r_{i})$-г сонгох хэрэгтэй ба дараа нь уг даалгавар $t_{i}$ нэгж хугацааны туршид хийгдэх ёстой буюу $s_{i}$ гэсэн цагт эхлээд $s_{i} + t_{i} - 1$ гэсэн цаг хүртэл хийгдэх ёстой гэсэн утгыг илэрхийлэх юм. Өөрөөр хэлбэл энэ 3-н бүхэл тоо нь уг даалгаврыг $t_{i}$ нэгж хугацааг дуустал гүйцэтгэх бөгөөд $l_{i}$ цагаас эрт эхлэх ёсгүй ба $r_{i}$ цагаас орой дуусаж болохгүй болохыг илэрхийлнэ.

Поликарпус-ын даалгаврууд нь үнэхээр содон шинжтэй байв. ямар ч $j, k$ ($j < k$)-ын хувьд $l_{j} < l_{k}$ бөгөөд $r_{j} < r_{k}$ байх ажээ.

$|A|$ ширхэг дараалалд оруулсан даалгавруудын олонлог $A$-г авч үзье. Бид $a_{j} = (l_{j}, r_{j}, t_{j})$ $(1 ≤ j ≤ |A|)$ гэж үзэх юм. Мөн бид даалгаврууд нь $l_{j}$ ихсэх дарааллын дагуу эрэмбэлэгдсэн гэж үзнэ.

Хариу нь нэгэн бүхэл тоо байх бөгөөд аргумент нь дараалалд оруулсан даалгавруудын олонлог $A$ байх $f$ рекурсив функцийг авч үзье. $f(A)$ функц нь нэгэн төвөгтэй алгоритмоор тодорхойлогдох бөгөөд доор уг алгоритмыг pseudo программчлалын хэл дээр дүрслэв.

  • Алхам 1. , $ans = 0$.
  • Алхам 2. Бид бүх даалгавруудыг тэдгээрийн $A$ олонлог доторх дугааруудын өсөх дарааллын дагуу авч үзэх юм. Одоогийн даалгавар тоологчийг $i = 0$ гэж тэмдэглэе.
  • Алхам 3. Дараагийн даалгаврыг авч үзнэ: $i = i + 1$. Хэрэв $i > |A|$ үнэн байвал шууд алхам 8 уруу шилжинэ.
  • Алхам 4. Хэрэв та даалгаврыг $s_{i}$ = max$(ans + 1, l_{i})$ гэсэн цагаас эхлэн гүйцэтгэж чадах болох $i$-р даалгаврыг гүйцэтгэнэ үү: $s_{i}$ = max($ans + 1$, $l_{i}$), $ans = s_{i} + t_{i} - 1$, . Дараа нь дараагийн даалгавар уруу шилжинэ (алхам 3).
  • Алхам 5. Бусад тохиолдолд дараах нөхцөлүүдийг хангах даалгаврыг олно. Нэгт $a_{i}$ даалгавар нь $s_{i}$ = max гэсэн цагт гүйцэтгэгдэж болдог байна. 2-т -ын утга нь эерэг байх бөгөөд энэ нь эхний нөхцөлийг хангах бүх $b_{k}$-ууд дундаас хамгийн их утгыг нь авч байна. Хэрэв та олон тооны даалгавруудыг $b_{k}$ болгон сонгож чадаж байвал $A$ олонлог доторх хамгийн их дугаартай нэгийг нь сонгоно уу.
  • Алхам 6. Хэрэв та $b_{k}$-г сонгосон бол , болох юм. Үүний дараа дараагийн даалгавар уруу шилжинэ (алхам 3).
  • Алхам 7. Хэрэв та $b_{k}$ даалгаврыг сонгож чадаагүй байгаа бол $i$-р даалгаврыг алгасна уу. Үүний дараа дараагийн даалгавар уруу шилжинэ (алхам 3).
  • Алхам 8. $ans$-г $f(A)$ функцийг гүйцэтгэсний хариу болгон буцаана.

Поликарпус эдгээр олон томьёо болон тодорхойлолтууд дунд толгой нь эргэж гүйцсэн бөгөөд таныг $f$ функцийг гүйцэтгэн $f(A)$-ын хариуг олж өгөхийг хүсжээ.

Оролт

Оролтын эхний мөрөнд ганц бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$) өгөгдөх ба энэ нь $A$ олонлог доторх даалгавруудын тоог илэрхийлнэ.

Дараагийн $n$ ширхэг мөрүүдэд даалгавруудыг дүрсэлнэ. $i$-р мөрөнд зайгаар тусгаарлагдсан 3-н бүхэл тоо $l_{i}$, $r_{i}$, $t_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ 10^{9}$, $1 ≤ t_{i} ≤ r_{i} - l_{i} + 1$)-ууд өгөгдөх ба эдгээр нь $i$-р даалгаврын тайлбарыг илэрхийлнэ.

Мөн ямар ч $j, k$ ($j < k$) даалгаврын хувьд дараах зүйлс үнэн байх юм: $l_{j} < l_{k}$ бөгөөд $r_{j} < r_{k}$ байна.

Гаралт

$i$-р даалгавар бүрийн хувьд ганц бүхэл тоог хэвлэх ба энэ нь $f(A)$ функцийн цикл буюу алхам 3-ын $i$-дахь давталт дээр $i$-р даалгаврыг гүйцэтгэсэн үр дүнг илэрхийлнэ. $i$-р мөрөнд дараах утгуудыг хэвлэнэ:

  • 0 -- Хэрэв та $i$-р даалгаврыг алхам 4 уруу оруулсан бол уг утгыг хэвлэнэ үү. Зарим даалгаврууд нь 3-р алхмаас шууд 5-р алхам уруу шилжиж байгааг анхаарна уу.
  • -1 -- Хэрэв та $i$-р даалгаврыг алхам 7 уруу оруулаагүй юм уу солиогүй бол уг утгыг хэвлэнэ үү.
  • $res_{i}$ ($1 ≤ res_{i} ≤ n$) -- Хэрэв та даалгаврыг сольсон байвал уг утгыг хэвлэнэ үү (алхам 6): $res_{i}$ нь $b_{k}$ болж сонгогдсон буюу $a_{i}$ даалгавраар солигдсон даалгаврын ($A$ олонлог доторх) дугаартай тэнцүү байна

Орчуулсан: Баатархүү

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

Оролт
5
1 8 5
2 9 3
3 10 3
8 11 4
11 12 2
Гаралт
0 0 1 0 -1 
Оролт
13
1 8 5
2 9 4
3 10 1
4 11 3
8 12 5
9 13 5
10 14 5
11 15 1
12 16 1
13 17 1
14 18 3
15 19 3
16 20 2
Гаралт
0 0 0 2 -1 -1 0 0 0 0 7 0 12 
Сэтгэгдлүүдийг ачааллаж байна...