結果

問題 No.2931 Shibuya 109
コンテスト
ユーザー detteiuu
提出日時 2025-10-06 22:58:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 868 ms / 4,000 ms
コード長 739 bytes
コンパイル時間 458 ms
コンパイル使用メモリ 82,612 KB
実行使用メモリ 194,168 KB
最終ジャッジ日時 2025-10-06 22:59:06
合計ジャッジ時間 14,046 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left, bisect_right

N, Q = map(int, input().split())
A = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(Q)]

cum = [0]
IDX = []
for i, a in enumerate(A):
    if a == 9:
        cum.append(cum[-1]+1)
    else:
        cum.append(cum[-1])
    if a == 1:
        IDX.append(i)

def SUM(l, r):
    return cum[r]-cum[l]

for L, R in query:
    L, R = L-1, R-1
    B = [L-1]
    idx = bisect_left(IDX, L)
    while idx < len(IDX) and IDX[idx] <= R:
        B.append(IDX[idx])
        idx += 1
    B.append(R+1)
    ans = 0
    for i in range(len(B)-1):
        if i+2 < len(B):
            ans += i
        l, r = B[i], B[i+1]
        ans += i*(r-l-1)+SUM(l+1, r)
    print(ans)
0