E. Numbers on the blackboard

Codeforces

IDCF878E

Time2000ms

Memory512MB

Difficulty—

combinatoricsdp

English · Original

Chinese · Translation

Formal · Original

A sequence of _n_ integers is written on a blackboard. Soon Sasha will come to the blackboard and start the following actions: let _x_ and _y_ be two adjacent numbers (_x_ before _y_), then he can remove them and write _x_ + 2_y_ instead of them. He will perform these operations until one number is left. Sasha likes big numbers and will get the biggest possible number. Nikita wants to get to the blackboard before Sasha and erase some of the numbers. He has _q_ options, in the option _i_ he erases all numbers to the left of the _l__i_\-th number and all numbers to the right of _r__i_\-th number, i. e. all numbers between the _l__i_\-th and the _r__i_\-th, inclusive, remain on the blackboard. For each of the options he wants to know how big Sasha's final number is going to be. This number can be very big, so output it modulo 109 + 7. ## Input The first line contains two integers _n_ and _q_ (1 ≤ _n_, _q_ ≤ 105) — the number of integers on the blackboard and the number of Nikita's options. The next line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 109 ≤ _a__i_ ≤ 109) — the sequence on the blackboard. Each of the next _q_ lines contains two integers _l__i_ and _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ _n_), describing Nikita's options. ## Output For each option output Sasha's result modulo 109 + 7. [samples] ## Note In the second sample Nikita doesn't erase anything. Sasha first erases the numbers 1 and 2 and writes 5. Then he erases 5 and _\-3_ and gets _\-1_. _\-1_ modulo 109 + 7 is 109 + 6.

一块黑板上写有一个包含 #cf_span[n] 个整数的序列。不久后，Sasha 将来到黑板前执行以下操作：设 #cf_span[x] 和 #cf_span[y] 是两个相邻的数（#cf_span[x] 在 #cf_span[y] 之前），他可以将它们移除，并用 #cf_span[x + 2y] 替代它们。他将重复执行这些操作，直到只剩下一个数。Sasha 喜欢大数，因此他会得到可能的最大值。 Nikita 希望在 Sasha 到来之前到达黑板并擦除一些数字。他有 #cf_span[q] 种选择，在第 #cf_span[i] 种选择中，他会擦除第 #cf_span[li]- 个数左侧的所有数字以及第 #cf_span[ri]- 个数右侧的所有数字，即只有位于第 #cf_span[li]- 个数和第 #cf_span[ri]- 个数之间（包含两端）的数字会留在黑板上。对于每种选择，他想知道 Sasha 最终得到的数字是多少。这个数字可能非常大，因此请输出其对 #cf_span[109 + 7] 取模的结果。第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n, q ≤ 105]) —— 黑板上整数的个数和 Nikita 的选择数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 109 ≤ ai ≤ 109]) —— 黑板上的序列。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ n])，描述 Nikita 的每种选择。对于每种选择，请输出 Sasha 的最终结果对 #cf_span[109 + 7] 取模的值。在第二个样例中，Nikita 没有擦除任何数字。Sasha 首先擦除数字 #cf_span[1] 和 #cf_span[2]，并写入 #cf_span[5]。然后他擦除 #cf_span[5] 和 _-3_，得到 _-1_。_ -1_ 对 #cf_span[109 + 7] 取模的结果是 #cf_span[109 + 6]。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n, q ≤ 105]) —— 黑板上整数的个数和 Nikita 的选择数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 109 ≤ ai ≤ 109]) —— 黑板上的序列。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ n])，描述 Nikita 的每种选择。 ## Output 对于每种选择，请输出 Sasha 的最终结果对 #cf_span[109 + 7] 取模的值。 [samples] ## Note 在第二个样例中，Nikita 没有擦除任何数字。Sasha 首先擦除数字 #cf_span[1] 和 #cf_span[2]，并写入 #cf_span[5]。然后他擦除 #cf_span[5] 和 _-3_，得到 _-1_。_ -1_ 对 #cf_span[109 + 7] 取模的结果是 #cf_span[109 + 6]。

**Definitions** Let $n, q \in \mathbb{Z}^+$ such that $1 \leq n, q \leq 10^5$. Let $A = (a_1, a_2, \dots, a_n)$ be a sequence of integers where $-10^9 \leq a_i \leq 10^9$. Let $M = 10^9 + 7$. **Objective Function** Define a function $\phi(l, r)$ for $1 \leq l \leq r \leq n$ representing the maximum value obtainable from the subsequence $(a_l, \dots, a_r)$: $$ \phi(l, r) = \begin{cases} a_l & \text{if } l = r \\ \max_{k=l}^{r-1} \left( \phi(l, k) + 2 \cdot \phi(k+1, r) \right) & \text{if } l < r \end{cases} $$ **Queries** Given $q$ pairs of indices $(l_j, r_j)$ where $1 \leq l_j \leq r_j \leq n$ for $j = 1, \dots, q$. **Output** For each $j \in \{1, \dots, q\}$, compute: $$ \phi(l_j, r_j) \pmod M $$

Samples

Input #1

Output #1

17
5
8

Input #2

3 1
1 2 -3
1 3

Output #2

1000000006

Input #3

Output #3

5
1000000006

API Response (JSON)

{
  "problem": {
    "name": "E. Numbers on the blackboard",
    "description": {
      "content": "A sequence of _n_ integers is written on a blackboard. Soon Sasha will come to the blackboard and start the following actions: let _x_ and _y_ be two adjacent numbers (_x_ before _y_), then he can rem",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF878E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A sequence of _n_ integers is written on a blackboard. Soon Sasha will come to the blackboard and start the following actions: let _x_ and _y_ be two adjacent numbers (_x_ before _y_), then he can rem...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一块黑板上写有一个包含 #cf_span[n] 个整数的序列。不久后，Sasha 将来到黑板前执行以下操作：设 #cf_span[x] 和 #cf_span[y] 是两个相邻的数（#cf_span[x] 在 #cf_span[y] 之前），他可以将它们移除，并用 #cf_span[x + 2y] 替代它们。他将重复执行这些操作，直到只剩下一个数。Sasha 喜欢大数，因此他会得到可能的最大值。\n\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**\n\nLet $n, q \\in \\mathbb{Z}^+$ such that $1 \\leq n, q \\leq 10^5$.\nLet $A = (a_1, a_2, \\dots, a_n)$ be a sequence of integers where $-10^9 \\leq a_i \\leq 10^9$.\nLet $M = 10^9 + 7$.\n\n**Obje...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments