問題一覧 > 通常問題

No.1290 Addition and Subtraction Operation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 32
作問者 : CinnamorollCinnamoroll / テスター : kyort0nkyort0n
7 ProblemId : 4669 / 出題時の順位表
問題文最終更新日: 2020-11-15 02:03:49

問題文

長さ$~N~$の整数列$~B = (B_1,B_2,...,B_N)~$と$~M~$個の整数の組$~(L_1,R_1),(L_2,R_2),...,(L_M,R_M)~$が与えられます。
あなたは長さ$~N~$の整数列$~A~$を持っています。はじめ、整数列$~A~$のすべての要素は$0$です。
以下の条件を満たす長さ$~M~$の整数列$~K=(K_1,K_2,...,K_M)~$が存在するか判定してください。

条件
$~1 \leq i \leq M~$であるすべての整数$~i~$について、操作$~i~$をちょうど1回ずつ行うことで整数列$~A~$と整数列$~B~$が一致する。
・操作$~i~$: $~L_i \leq j \leq R_i~$であるすべての整数$~j~$に対して$~A_j~$に$~K_i \times (-1)^{j-L_i}~$ を加算する。

入力

$N~~~M$
$B_1~~B_2~~..~~B_N$
$L_1~~R_1$
$L_2~~R_2$
:
$L_M~~R_M$

・$1 \leq N \leq 10^5 $
・$0 \leq M \leq 10^5 $
・$-10^9 \leq B_i \leq 10^9$
・$1 \leq L_i \leq R_i \leq N$
・$i \neq j$ならば$~~(L_i,R_i) \neq (L_j,R_j)$
・入力はすべて整数

出力

条件を満たす整数列$K$が存在するならば 'YES'と 、そうでないならば 'NO' と出力せよ。

サンプル

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

$K=(1,-4)$が条件を満たします。

サンプル2
入力
3 2
2 -1 0
1 2
2 3
出力
NO

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