結果

問題 No.3244 Range Multiple of 8 Query
ユーザー amesyu
提出日時 2025-08-23 00:09:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,373 bytes
コンパイル時間 388 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 116,164 KB
最終ジャッジ日時 2025-08-23 00:09:47
合計ジャッジ時間 34,054 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 15 WA * 8 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n, q = map(int, input().split())
s = list(map(int, input()))

pos = [[] for _ in range(10)]
for i in range(n):
    pos[s[i]].append(i)

search = []
for x in range(104, 1000, 8):
    if "0" not in str(x):
        search.append(list(map(int, str(x))))
inf = int(1e9)

for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    size = r - l

    if size == 1:
        print(0 if s[l] == 8 else -1)
    elif size == 2:
        if (s[l] * 10 + s[l + 1]) % 8 == 0:
            print(0)
        elif (s[l + 1] * 10 + s[l]) % 8 == 0:
            print(1)
        else:
            print(-1)
    else:
        init = [bisect.bisect_left(pos[i], r) - 1 for i in range(10)]
        ans = int(1e9)
        for x2, x1, x0 in search:
            ptr = [init[i] for i in range(10)]
            t = []
            if ptr[x0] == -1 or pos[x0][ptr[x0]] < l:
                continue
            t.append(max(0, (r - 1) - pos[x0][ptr[x0]]))
            ptr[x0] -= 1
            if ptr[x1] == -1 or pos[x1][ptr[x1]] < l:
                continue
            t.append(max(0, (r - 2) - pos[x1][ptr[x1]]))
            ptr[x1] -= 1
            if ptr[x2] == -1 or pos[x2][ptr[x2]] < l:
                continue
            t.append(max(0, (r - 3) - pos[x2][ptr[x2]]))
            ptr[x2] -= 1
            ans = min(ans, sum(t))

        print(-1 if ans == inf else ans)
0