結果

問題 No.3244 Range Multiple of 8 Query
ユーザー tassei903
提出日時 2025-08-22 23:31:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 4,697 ms / 5,000 ms
コード長 2,459 bytes
コンパイル時間 871 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 156,084 KB
最終ジャッジ日時 2025-08-22 23:32:24
合計ジャッジ時間 77,278 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
inf = 10 ** 18
# 2桁以下は愚直
# 末尾の3桁を125通り試す
# 
n, q = na()
s = [int(i) for i in input()]
F = [[] for i in range(n + 1)]
que = []
for i in range(q):
    l, r = na()
    l -= 1
    que.append((l, r))
    if r - l >= 3:
        F[r].append(i)
D = []
for i in range(104, 1000, 8):
    x = str(i)
    if "0" in x or len(x) != 3:
        continue
    D.append([int(x[0]), int(x[1]), int(x[2])])
# print(D)
lis = [[-inf, -inf, -inf] for i in range(10)]
ans = [inf] * q
def inv(x):
    # ans = 0
    # for i in range(3):
    #     for j in range(i+1, 3):
    #         if x[i] < x[j]:
    #             ans += 1
    # return ans
    return int(x[0] < x[1]) + int(x[0] < x[2]) + int(x[1] < x[2])
A = [2] * 10
for r in range(1, n + 1):
    F[r] = sorted(F[r], key = lambda ii:-que[ii][0])
for r in range(1, n + 1):
    lis[s[r-1]] = [lis[s[r-1]][1], lis[s[r-1]][2], r-1]
    # print(r, lis[9])
    for x in D:
        ANS = inf
        for i in F[r]:
            if ANS != inf:
                ans[i] = min(ans[i], ANS)
                continue
            l = que[i][0]        
            # if x[0] == x[1] == x[2]:
            #     if lis[x[0]][0] >= l:
            #         ans[i] = min(ans[i], (r-1 + r-2 + r-3)-sum(lis[x[0]]))
            # elif 
            
            ff = []
            for j in range(2, -1, -1):
                if lis[x[j]][A[x[j]]] >= l:
                    ff.append(lis[x[j]][A[x[j]]])
                    A[x[j]] -= 1
                else:
                    break
            else:
                ans[i] = min(ans[i], (r-1 + r-2 + r-3) - sum(ff) + inv(ff))
                ANS = ans[i]
            A[x[0]] = A[x[1]] = A[x[2]] = 2


for i in range(q):
    l, r = que[i]
    if r - l == 1:
        if s[l] == 8:
            print(0)
        else:
            print(-1)
    elif r - l == 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:
        if ans[i] == inf:
            print(-1)
        else:
            print(ans[i])
0