結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー detteiuu
提出日時 2025-08-22 22:31:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,194 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 157,072 KB
最終ジャッジ日時 2025-08-22 22:31:25
合計ジャッジ時間 18,473 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 18 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

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
    ans = INF
    for n in range(0, 100, 4):
        s = str(n)
        r = int(s[-1])
        if len(s) == 2:
            l = int(s[0])
        else:
            l = 0
        b = bisect_right(IDX[r], R)
        idxR = IDX[r][b-1] if 1 <= b else -1
        b = bisect_right(IDX[l], R)
        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 = bisect_right(IDX2[odd], R)-1
        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