Gaps of 1 or 2

AtCoder

IDarc190_e

Time5000ms

Memory256MB

Difficulty—

You are given a length-$N$ sequence $A = (A_1, \ldots, A_N)$ of non-negative integers. Answer $Q$ queries. In the $i$\-th query, you are given integers $L_i$ and $R_i$ such that $1 \leq L_i \leq R_i \leq N$. Solve the following problem for the subsequence $B = (A_{L_i}, \ldots, A_{R_i})$ of length $R_i - L_i + 1$. > We repeat the following operation on $B$: > > * Choose integers $i$ and $j$ with $1 \leq i, j \leq |B|$ such that $B_i \ge 1$, $B_j \ge 1$, and $1 \leq j - i \leq 2$. Subtract $1$ from $B_i$ and $B_j$. > > Find the maximum number of times the operation can be performed. ## Constraints * $1 \leq N \leq 200000$ * $1 \leq Q \leq 200000$ * $0 \leq A_i \leq 10^9$ * $1 \leq L_i \leq R_i \leq N$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $Q$ $A_1$ $\cdots$ $A_N$ $L_1$ $R_1$ $\vdots$ $L_Q$ $R_Q$ [samples]

Samples

Input #1

6 1
1 1 4 0 3 2
1 6

Output #1

5

In this example, we solve the problem for $B = (1,1,4,0,3,2)$. We can perform five operations as follows:

*   Choose $i=1$ and $j=3$. Then $B = (0,1,3,0,3,2)$.
*   Choose $i=2$ and $j=3$. Then $B = (0,0,2,0,3,2)$.
*   Choose $i=3$ and $j=5$. Then $B = (0,0,1,0,2,2)$.
*   Choose $i=5$ and $j=6$. Then $B = (0,0,1,0,1,1)$.
*   Choose $i=5$ and $j=6$. Then $B = (0,0,1,0,0,0)$.

Input #2

6 6
49 83 10 77 21 62
1 1
1 2
1 3
3 5
1 6
5 6

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Gaps of 1 or 2",
    "description": {
      "content": "You are given a length-$N$ sequence $A = (A_1, \\ldots, A_N)$ of non-negative integers. Answer $Q$ queries. In the $i$\\-th query, you are given integers $L_i$ and $R_i$ such that $1 \\leq L_i \\leq R_i \\",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc190_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a length-$N$ sequence $A = (A_1, \\ldots, A_N)$ of non-negative integers. Answer $Q$ queries.\nIn the $i$\\-th query, you are given integers $L_i$ and $R_i$ such that $1 \\leq L_i \\leq R_i \\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments