Fișierul de ieșire $cartita.out$ va conține *Q* linii, pe fiecare găsindu-se, în ordine, răspunsul la intervalele investigate.
h2. Restricții
h2. Restricții și precizări
* $... ≤ ... ≤ ...$
* $1 ≤ *N* ≤ 100 000$
* $1 ≤ *U* ≤ 300 000$
* $1 ≤ *Q* ≤ 200 000$
* $1 ≤ *L* ≤ *R* ≤ [*N*]$
* $Inițial 1 ≤ h[i] ≤ N, pentru fiecare i, 1 ≤ i ≤ N$
* $1 ≤ pos ≤ N , [*1 ≤ x ≤ 400 și −21 ≤ K ≤ 21*], K ≠ 0$
* $Subtask 1 – *12* puncte: N, U, Q ≤ 2 000$
* $Subtask 2 – *9* puncte: N, U ≤ 2 000 și Q ≤ 200 000$
* $Subtask 3 – *25* de puncte: N, U ≤ 75 000 și Q ≤ 15$
* $Subtask 4 – *17* puncte: N, U, Q ≤ 75 000$
* $Subtask 5 – *16* puncte: N ≤ 100 000, U ≤ 300 000 și Q ≤ 15$
* $Subtask 6 – *7* puncte: N ≤ 100 000, U ≤ 300 000 și Q ≤ 10 000$
* $Subtask 7 – *14* puncte: Nu există restricții suplimentare.$
h2. Exemplu
table(example).
|_. cartita.in |_. cartita.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 6
1 6 2 4 3 4
3
4 5 2
2 4 1
4 2 8
3
1 6
2 4
4 4
| -19
-3
17 |
h3. Explicație
...
* După prima galerie săpată către morcovul 4, șirul înălțimilor celor $N = 6$ grămăjoare a devenit [$(0, 7, 5, 9, 10, 13)$].
* După a doua galerie săpată către morcovul 2, șirul înălțimilor celor $N = 6$ grămăjoare a devenit [$(3, 11, 10, 15, 17, 21)$].
* După a treia galerie săpată către morcovul 4, șirul înălțimilor celor $N = 6$ grămăjoare a devenit [$(−19, −3, 4, 17, 27, 39)$]
* Pe intervalul [$[1, 6]$], înălțimea minimă este [$−19$], pe intervalul [$[2, 4]$], înălțimea minimă este [$−3$], iar pentru ultimul interval investigat [$[4, 4]$] înălțimea minimă este [$17$].
== include(page="template/taskfooter" task_id="cartita") ==
