結果

問題 No.3244 Range Multiple of 8 Query
ユーザー AngrySadEight
提出日時 2025-08-09 00:38:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,576 ms / 5,000 ms
コード長 1,816 bytes
コンパイル時間 297 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 169,620 KB
最終ジャッジ日時 2025-08-09 00:39:29
合計ジャッジ時間 47,312 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

def inv(x1, x2, x3):
    ret = 0
    if x1 > x2:
        ret += 1
    if x1 > x3:
        ret += 1
    if x2 > x3:
        ret += 1
    return ret

N, Q = map(int, input().split())
S = str(input())
l = []
r = []

for _ in range(Q):
    L, R = map(int, input().split())
    l.append(L)
    r.append(R)

prev_idx = [[[-1 for _ in range(N + 1)] for _ in range(10)] for _ in range(3)]
for i in range(N):
    val = int(S[i])
    for j in range(1, 10):
        if val == j:
            prev_idx[0][j][i + 1] = i + 1
            for k in range(2):
                prev_idx[k + 1][j][i + 1] = prev_idx[k][j][i]
        else:
            for k in range(3):
                prev_idx[k][j][i + 1] = prev_idx[k][j][i]

mul_8 = []
for i in range(0, 1000, 8):
    sr = str(1000 + i)
    if '0' not in sr:
        mul_8.append(i)

INF = 10 ** 10 + 23

vec_cnt = [0 for _ in range(10)]
for i in range(Q):
    if l[i] == r[i]:
        if S[l[i] - 1] == '8':
            print(0)
        else:
            print(-1)
        continue
    elif l[i] + 1 == r[i]:
        fs = S[l[i] - 1 : r[i]]
        rs = fs[1] + fs[0]

        if int(fs) % 8 == 0:
            print(0)
        elif int(rs) % 8 == 0:
            print(1)
        else:
            print(-1)
        continue
    ans = INF
    for x in mul_8:
        t1 = x % 10
        t2 = (x // 10) % 10
        t3 = x // 100

        id1 = prev_idx[vec_cnt[t1]][t1][r[i]]
        vec_cnt[t1] += 1
        id2 = prev_idx[vec_cnt[t2]][t2][r[i]]
        vec_cnt[t2] += 1
        id3 = prev_idx[vec_cnt[t3]][t3][r[i]]

        vec_cnt[t1] -= 1
        vec_cnt[t2] -= 1

        if id1 < l[i] or id2 < l[i] or id3 < l[i]:
            continue
        ans = min(ans, 3 * r[i] - 3 - id1 - id2 - id3 + inv(id3, id2, id1))
    if ans == INF:
        print(-1)
    else:
        print(ans)
0