問題一覧 > 通常問題

No.1675 Strange Minimum Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 131
作問者 : 👑 stoqstoq / テスター : akakimidoriakakimidori hanyuhanyu
13 ProblemId : 4295 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-07 20:40:23

問題文

次のような問題があります。

問題文:
長さ $N$ の数列 $A_1, A_2, \cdots, A_N$ があります。次の $Q$ 個のクエリに答えてください。
・ $i$ 個目のクエリでは整数 $l_i, r_i$ が与えられる。 $A_{l_i}, A_{l_i + 1}, \cdots, A_{r_i}$ の最小値を求めよ。

制約:
$1 \leq N,Q \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
$1 \leq l_i \leq r_i \leq N \ (1 \leq i \leq Q)$

yukiさんはこの問題を解いたところ、 $i$ 番目のクエリに対する解が $B_i$ となりました。

しかし問題を解いた後で数列 $\{ A_i \}$ を紛失してしまったため、本当に答えが合っているのかどうかわからなくなってしまいました。

制約を満たし、かつクエリに対する解が全て一致する数列 $\{ A_i \}$ が存在するならそれを1つ構築し、存在しないなら-1を出力してください。

入力

$N \ Q$
$l_1 \ r_1 \ B_1$
$\vdots$
$l_Q \ r_Q \ B_Q$

  • 入力は全て整数
  • $1 \leq N,Q \leq 2 \times 10^5$
  • $1 \leq B_i \leq 10^9$
  • $1 \leq l_i \leq r_i \leq N$

出力

$1$ 以上 $10^9$ 以下の整数から成り、任意の $i \ (1 \leq i \leq Q)$ に対し $A_{l_i}, A_{l_i + 1}, \cdots, A_{r_i}$ の最小値が $B_i$ となる長さ $N$ の数列 $\{ A_i \}$ が存在するならその一例を、存在しないなら-1を出力してください。

空白区切りで出力し、最後に改行してください(-1の場合も改行してください)。
末尾に余分な空白がある、改行がないなどの場合不正解となるので注意してください。

サンプル

サンプル1
入力
5 3
1 3 1
3 5 3
4 5 4
出力
2 1 3 5 4

数列 $2,1,3,5,4$ は

  • $A_1,A_2,A_3$ の最小値は $1$
  • $A_3,A_4,A_5$ の最小値は $3$
  • $A_4,A_5$ の最小値は $4$
より、全てのクエリについて条件を満たします。

他にも条件を満たす数列は存在しますが、そのうちのどれを出力しても構いません。

サンプル2
入力
3 2
1 2 2
1 1 1
出力
-1
条件を満たす数列は存在しません。

サンプル3
入力
4 3
1 3 1
2 4 1
1 4 1
出力
1 1 1 1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。