No.1290 Addition and Subtraction Operation
タグ : / 解いたユーザー数 49
作問者 :
Cinnamoroll
/ テスター :
kyort0n
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もしくは右上の雲マークをクリックしてアカウントを作成してください。