/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
高橋くんは秘密の整数列 a を持っており、現時点で、a の長さが N であることは分かっています。
a の中身を当てたいあなたに対し、高橋くんは以下の Q 個の情報を追加で与えてくれることを約束しました。
- i\ (1 \leq i \leq Q) 個目の情報: a_{l_i}+a_{l_i+1}+\cdots+a_{r_i} の値
高橋くんが約束を守り、Q 個の情報すべてが与えられた場合、a に含まれる全要素の総和 a_1+a_2+\cdots+a_N を特定することは可能ですか？
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq \min(2 \times 10^5,\frac{N(N+1)}{2})
- 1 \leq l_i \leq r_i \leq N
- (l_i,r_i) \neq (l_j,r_j)\ (i \neq j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N Q
l_1 r_1
l_2 r_2
\hspace{0.4cm}\vdots
l_Q r_Q
出力
a に含まれる全要素の総和を特定することが可能なら Yes を、そうでないなら No を出力せよ。
入力例 1
3 3 1 2 2 3 2 2
出力例 1
Yes
1 個目の情報と 2 個目の情報から、a_1+a_2+a_2+a_3 の値が分かります。そこから 3 個目の情報によって得られる a_2 の値を引くと、a_1+a_2+a_3 の値を特定可能です。
入力例 2
4 3 1 3 1 2 2 3
出力例 2
No
a の先頭 3 項の総和を特定することは可能ですが、全要素の総和を特定することは不可能です。
入力例 3
4 4 1 1 2 2 3 3 1 4
出力例 3
Yes
4 個目の情報によって全要素の総和が直接与えられています。
Score : 500 points
Problem Statement
Takahashi has a secret integer sequence a. You know that the length of a is N.
You want to guess the contents of a. He has promised to give you the following Q additional pieces of information.
- The i-th information: the value a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}.
Is it possible to determine the sum of all elements in a, a_1+a_2+\cdots+a_N, if the Q pieces of promised information are given?
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq \min(2 \times 10^5,\frac{N(N+1)}{2})
- 1 \leq l_i \leq r_i \leq N
- (l_i,r_i) \neq (l_j,r_j)\ (i \neq j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q
l_1 r_1
l_2 r_2
\hspace{0.4cm}\vdots
l_Q r_Q
Output
If it is possible to determine the sum of all elements in a, print Yes; otherwise, print No.
Sample Input 1
3 3 1 2 2 3 2 2
Sample Output 1
Yes
From the first and second information, we can find the value a_1+a_2+a_2+a_3. By subtracting the value of a_2 from it, we can determine the value a_1+a_2+a_3.
Sample Input 2
4 3 1 3 1 2 2 3
Sample Output 2
No
We can determine the sum of the first 3 elements of a, but not the sum of all elements.
Sample Input 3
4 4 1 1 2 2 3 3 1 4
Sample Output 3
Yes
The fourth information directly gives us the sum of all elements.