Range Sums

AtCoder

IDabc238_e

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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$.

Input #2

Output #2

No

We can determine the sum of the first $3$ elements of $a$, but not the sum of all elements.

Input #3

Output #3

Yes

The fourth information directly gives us the sum of all elements.

API Response (JSON)

{
  "problem": {
    "name": "Range Sums",
    "description": {
      "content": "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 informati",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc238_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi has a secret integer sequence $a$. You know that the length of $a$ is $N$.\nYou want to guess the contents of $a$. He has promised to give you the following $Q$ additional pieces of informati...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments