問題一覧 > 通常問題

No.2931 Shibuya 109

レベル : / AI推定難易度 : 1350 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 46
作問者 : kusirakusira / テスター : hirayuu_yc nouka28 👑 loop0919 tnodino amesyu uruzunyaa
お気に入りにしたユーザー ProblemId : 11323 / 自分の提出
問題文最終更新日: 2024-10-12 14:04:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第3回緑以下コンテスト エキストラ (順位表) の他の問題:

Problem Statement

There is a sequence $A$ of length $N$ consisting of 1, 0, and 9.
For a pair of integers $(l, r)$ satisfying $1 \le l \le r \le N$, define the function $f(l ,r)$ as follows.

$f(l, r) :=$ the value obtained by regarding the $l$-th through $r$-th elements of the sequence $A$ as strings, concatenating them, and regarding the result as a number in base $10$
Find the digit sum of $\left\lfloor\frac{f(l, r)}{9}\right\rfloor$.

Answer $Q$ queries.

What is the digit sum? The digit sum of a positive integer $n$ is defined as the sum of its digits when written in base $10$. For example, the digit sum of $2024$ is $2+0+2+4=8$.

Constraints

  • $1 \le N, Q \le 5 \times 10^5$
  • $A_i \in$ {$0, 1, 9$}
  • $1 \le l \le r \le N$
  • $A_l \neq 0$
  • There are at most $8$ indices $i$ satisfying $A_i = 1 \ (1 \le i \le N)$
  • All input values are integers

Input

The input is given from standard input in the following format.

$N\ Q$
$A_1\ A_2\ \cdots\ A_N$
$l_1\ r_1$
$l_2\ r_2$
$\vdots$
$l_Q r_Q$

Output

Print $Q$ lines. On line $i$ $(1 \leqq i \leqq Q)$, print the answer to the $i$-th query.

Sample

Sample 1
Input
9 3
1 0 9 1 0 9 1 0 9
3 5
1 4
1 9
Output
2
4
18

For the first case, the value obtained by concatenating the $3$-rd through $5$-th elements of the sequence $A$ as strings is $910$, so $f(3, 5)$ is $910$.
Since $\left\lfloor\frac{f(3, 5)}{9}\right\rfloor = \left\lfloor\frac{910}{9}\right\rfloor = 101$, the digit sum is $2(=1+0+1)$.

Sample 2
Input
23 8
1 0 1 9 1 0 1 0 0 0 9 1 9 9 0 9 1 0 0 0 0 1 1
4 20
5 22
1 19
11 22
3 14
13 20
3 3
22 23
Output
44
51
74
19
33
6
0
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。