結果

問題 No.3244 Range Multiple of 8 Query
ユーザー detteiuu
提出日時 2025-08-22 22:50:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,634 ms / 5,000 ms
コード長 1,485 bytes
コンパイル時間 374 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 146,244 KB
最終ジャッジ日時 2025-08-22 22:51:28
合計ジャッジ時間 45,463 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left, bisect_right

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

INF = 1<<60

IDX = [[] for _ in range(10)]
IDX2 = [[] for _ in range(2)]
for i, s in enumerate(S):
    n = int(s)
    IDX[n].append(i)
    IDX2[n%2].append(i)

for L, R in LR:
    L, R = L-1, R-1
    if L == R and S[L] == "8":
        print(0)
        continue
    if L+1 == R:
        if int(S[L:R+1])%8 == 0:
            print(0)
        elif int(S[R]+S[L])%8 == 0:
            print(1)
        else:
            print(-1)
        continue
    ans = INF
    B = [-1]*10
    for i in range(1, 10):
        B[i] = bisect_right(IDX[i], R)
    B2 = [-1]*2
    for i in range(2):
        B2[i] = bisect_right(IDX2[i], R)-1
    for n in range(12, 100, 4):
        s = str(n)
        r = int(s[1])
        l = int(s[0])
        b = B[r]
        idxR = IDX[r][b-1] if 1 <= b else -1
        b = B[l]
        idxL = IDX[l][b-1] if 1 <= b else -1
        if idxL == idxR:
            idxL = IDX[l][b-2] if 2 <= b else -1
        if min(idxL, idxR) < L:
            continue
        odd = 0 if n%8 == 0 else 1
        b = B2[odd]
        while 0 <= b and IDX2[odd][b] in [idxL, idxR]:
            b -= 1
        if b == -1 or IDX2[odd][b] < L:
            continue
        idx = IDX2[odd][b]
        SUM = R*3-idxL-idxR-idx-3
        SUM += (idxR < idxL)+(idxL < idx)+(idxR < idx)
        ans = min(ans, SUM)
    print(ans if ans != INF else -1)
0