問題一覧 > 通常問題

No.2931 Shibuya 109

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : kusirakusirakusirakusira / テスター : hirayuu_ychirayuu_yc nouka28nouka28 loop0919loop0919 tnodinotnodino amesyuamesyu Nyaa UruzuNyaa Uruzu
4 ProblemId : 11323 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-12 14:04:56

問題文

1, 0, 9 のいずれかからなる長さ $N$ の数列 $A$ があります。
$1 \le l \le r \le N$なる整数組 $(l, r)$ に対し、関数 $f(l ,r)$ を次のように定義します。

$f(l, r) :=$ 数列 $A$ の $l$ 番目から $r$ 番目までを文字列とみなして結合し、それを$10$ 進数の数とみなしたときの値
$\left\lfloor\frac{f(l, r)}{9}\right\rfloor$ の桁和を答えてください。

$Q$ 個のクエリに答えてください。

桁和とは 正整数 $n$ の桁和を $10$ 進法で表したときの各桁の和として定義します。例えば $2024$ の桁和は $2+0+2+4=8$ です。

制約

  • $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$
  • $A_i = 1 \ (1 \le i \le N)$を満たす $i$ は高々 $8$ 個
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えらる。

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

出力

$Q$ 行出力せよ。$i$ 個目のクエリの答えを $i$ 行目 $(1 \leqq i \leqq Q)$に出力せよ。

サンプル

サンプル1
入力
9 3
1 0 9 1 0 9 1 0 9
3 5
1 4
1 9
出力
2
4
18

1つめのケースについて、数列 $A$ の $3$ 番目から $5$ 番目を文字列として結合した値は $910$ であり、$f(3, 5)$ は $910$ です。
$\left\lfloor\frac{f(3, 5)}{9}\right\rfloor = \left\lfloor\frac{910}{9}\right\rfloor = 101$ であるため、桁和は $2(=1+0+1)$です。

サンプル2
入力
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
出力
44
51
74
19
33
6
0
1

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