問題一覧 > 通常問題

No.1290 Addition and Subtraction Operation

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 49
作問者 : Cinnamoroll / テスター : kyort0n
お気に入りにしたユーザー ProblemId : 4669 / 自分の提出
問題文最終更新日: 2020-11-15 02:03:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 274 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $~B = (B_1,B_2,...,B_N)~$ of length $~N~$ and $~M~$ pairs of integers $~(L_1,R_1),(L_2,R_2),...,(L_M,R_M)~$.
You have an integer sequence $~A~$ of length $~N~$. Initially, all elements of the integer sequence $~A~$ are $0$.
Determine whether there exists an integer sequence $~K=(K_1,K_2,...,K_M)~$ of length $~M~$ that satisfies the following condition.

Condition
By performing operation $~i~$ exactly once for every integer $~i~$ with $~1 \leq i \leq M~$, the integer sequence $~A~$ becomes equal to the integer sequence $~B~$.
・Operation $~i~$: For every integer $~j~$ with $~L_i \leq j \leq R_i~$, add $~K_i \times (-1)^{j-L_i}~$ to $~A_j~$.

Input

$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$
・If $i \neq j$, then $~~(L_i,R_i) \neq (L_j,R_j)$
・All input values are integers

Output

Print 'YES' if there exists an integer sequence $K$ satisfying the condition, and 'NO' otherwise.

Sample

Sample 1
Input
4 2
1 -5 5 -4
1 3
2 4
Output
YES

$K=(1,-4)$ satisfies the condition.

Sample 2
Input
3 2
2 -1 0
1 2
2 3
Output
NO

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