P9312 [EGOI 2021] Lanterns / Lanterns

Day 1 Problem D. The statement is translated from [EGOI2021 lantern](https://stats.egoi.org/media/task_description/2021_lantern_en.pdf).

Farmer John took his herd of cows on a hike in the Alps. After some time, it got dark and the hike ended. However, some cows are still trapped in different parts of the mountains, and now John needs to rescue them. The mountains the herd is traveling through are represented by $n$ points in the Cartesian plane. We call these points “peaks”. The peaks are numbered from $1$ to $n$ in order. Peak $i$ has coordinates $(i,h_i)$. The value $h_i$ represents the **altitude** of peak $i$. It is guaranteed that $h_1,h_2,\ldots,h_n$ form a permutation of $1\sim n$. Peak $i$ and peak $i+1$ are connected by a line segment. Since it is night, John must carry at least one lantern that is working properly in order to move in the mountains. Fortunately, there are $k$ lanterns available for purchase. Lantern $j$ can be bought at peak $p_j$ for $c_j$ francs. Unfortunately, lantern $j$ works properly only when John’s altitude is in $[a_j,b_j]$. In other words, if John’s altitude is strictly lower than $a_j$ or strictly higher than $b_j$, lantern $j$ will not work properly. Note that the lantern does not break when leaving this altitude range. For example, when John’s altitude exceeds $b_j$, lantern $j$ stops working, but as soon as John returns to altitude $b_j$, the lantern starts working again. If John is currently at peak $p$, he can do one of the following three actions: - He can buy a lantern sold at $p$. After buying it, he can use it forever. - If $p > 1$, he can walk to peak $p-1$. - If $p < n$, he can walk to peak $p+1$. John cannot move when he has no properly working lantern. He must ensure that at every moment there is at least one lantern working properly in order to move between two peaks. (During walking, it does not have to be the same lantern.) For example, suppose Farmer John is currently on a peak with altitude $4$ and wants to walk to a neighboring peak with altitude $1$. If John has two lanterns with altitude ranges $[1,3]$ and $[3,4]$, he can walk from one peak to the other. However, if John only has two lanterns with altitude ranges $[1,1]$ and $[2,5]$, he cannot walk between these two peaks. For instance, he has no lantern that can work properly at altitude $1.47$. You need to answer multiple independent queries. For each $1\le j\le k$ such that $a_j\le h_{p_j}\le b_j$, suppose John starts at peak $p_j$ and buys lantern $j$. To search the entire mountain range, he must repeatedly perform the three actions described above. For each $j$, compute the minimum number of francs John must spend in order to search the entire mountain range. (This cost includes the initial purchase of lantern $j$.)

The first line contains two integers $n,k$ — the number of peaks and the number of lanterns. The second line contains $n$ integers $h_1,h_2,\ldots,h_n$, the altitude of each peak. It is guaranteed that $h_i$ form a permutation of $1\sim n$. The next $k$ lines each contain four integers $p_j,c_j,a_j,b_j$ — the selling position, price, and altitude range of lantern $j$.

For each $1\le j\le k$, output one line: - If $h_{p_j}$ is not in $[a_j,b_j]$, output $-1$. - Otherwise, if John cannot search the entire mountain range when he initially buys lantern $j$, output $-1$. - Otherwise, output the minimum cost in this case.

**Sample Explanation** If John starts from peak $3$ and buys lantern $1$, he can do the following: - Walk left twice to reach peak $1$. - Buy lantern $2$. - Walk right to peak $4$. - Buy lantern $3$. - Walk right to peak $7$. Now John has visited every peak at least once, and he spent $1+2+4=7$ francs. John cannot start by buying lanterns $2,6,7$, because they do not work at the altitude where they are purchased. Therefore, their answers are $-1$. If John starts by buying lantern $3$ or $4$, he can visit every peak without buying any other lantern. If John starts by buying lantern $5$, he must buy lantern $4$. If John starts by buying lantern $8$, he will get stuck at peak $7$. Even if he buys lantern $7$, he still cannot move from peak $7$ to peak $6$. --- **Constraints** For all testdata, $1\le n,k\le 2\times 10^3$, $1\le h_i\le n$ and $h_i$ form a permutation of $1\sim n$, $1\le p_j\le n$, $1\le c_j\le 10^6$, $1\le a_j\le b_j\le n$. - Subtask 1 ($9$ points): $n\le 20$, $k\le 6$. - Subtask 2 ($12$ points): $n,k\le 70$. - Subtask 3 ($23$ points): $n,k\le 300$, $h_i=i$. - Subtask 4 ($16$ points): $n,k\le 300$. - Subtask 5 ($40$ points): no special constraints. Translated by ChatGPT 5