No.1675 Strange Minimum Query

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1675 Strange Minimum Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題（複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 154
作問者 :

stoq / テスター :

akakimidori

hanyu

14 ProblemId : 4295 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-08-07 20:40:23

問題文

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

問題文：
長さ  $N$  の数列  $A_{1}, A_{2}, \dots, A_{N}$  があります。次の  $Q$  個のクエリに答えてください。
・  $i$  個目のクエリでは整数  $l_{i}, r_{i}$  が与えられる。  $A_{l_{i}}, A_{l_{i} + 1}, \dots, 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}$ 
 $⋮$ 
 $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}, \dots, A_{r_{i}}$ の最小値が $B_{i}$ となる長さ $N$ の数列 ${A_{i}}$ が存在するならその一例を、存在しないなら-1を出力してください。

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

サンプル

サンプル1

入力

出力

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

入力

出力

1 1 1 1

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

yukicoder

No.1675 Strange Minimum Query

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力