問題概要

以下の条件を満たす整数列 $(A_1,A_2,...,A_N)$ を一つ求めよ。存在しなければ-1を出力せよ。

$1\leq A_i\leq 10^9$
$\displaystyle\min_{k=l_i}^{r_i}A_k=B_i\ (1\leq i\leq Q)$

僕の解法

「$\displaystyle\min_{k=l_i}^{r_i}A_k=B_i$」と、「$A_k\geq B_i\ (l_i\leq k\leq r_i)$（条件1）かつ任意の $i$ について $A_k=B_i\ (l_i\leq k\leq r_i)$ を満たす $k$ が存在する（条件2）」は同値です。
そのうえで、以下の事実について考えます。

整数列 $A$ と $A'$ があり、どちらも問題の条件を満たすとする。
このとき、$A_k>A'_k$ を満たす全ての $k$ について、$A_k=A'_k$ と置き換えてもその数列は問題の条件を満たす。

条件1と条件2それぞれについて考えます。

条件1

$A_k\geq B_i\ (l_i\leq k\leq r_i)$ であり、かつ $A'_k\geq B_i\ (l_i\leq k\leq r_i)$ であるため、$\min(A_k,A'_k)\geq B_i\ (l_i\leq k\leq r_i)$ も満たします。（証明終）

条件2

$A_k> A'_k$ である時、 $A_k> A'_k\geq B_i$ あるため、必ず $A_k\neq B_i$ です。
そのため、$A_k=A'_k$ に置き換えた結果条件2を満たさなくなるということはありません。
また、$A$ も $A'$ も条件2を満たしているため、要素を置き換えた後も条件2は満たしたままです。（証明終）

この事実に基づいて考えると、$A_i$ は問題の条件を満たす限りできるだけ小さくして損がないということがわかります。逆に、できるだけ小さくしてもそれが問題の条件を満たさない場合、解は存在しないといううことも言えます。

このうえで、$A$ を左から順に決めていくことを考えます。
$A_k$ について考えるとき、全ての $l_i\leq k\leq r_i$ を満たす全ての $i$ について、$B_i\leq A_k$ である必要があります。そのうえで先ほどの事実で考えると、$l_i\leq k\leq r_i$ を満たす最大の $B_i$ を $A_i$ にするのが最適ということになります。最適な $A$ の求め方については、priority_queueを使えば $O((N+Q)\log Q)$ で見つけられます。

次に、この $A$ が問題の条件を満たすかを判定する必要があります。これはsparse tableやsegtreeを用いれば $O(Q\log N)$ で求められます。（確かこれは $O(Q)$ で求められた気がしますがここでは気にしないものとします）

以上より $O((N+Q)\log Q+Q\log N)$ でこの問題を解くことができました。

実装例

priority_queue+segtreeで書きました。