結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー tassei903
提出日時 2025-08-22 23:03:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,262 bytes
コンパイル時間 392 ms
コンパイル使用メモリ 82,852 KB
実行使用メモリ 137,896 KB
最終ジャッジ日時 2025-08-22 23:04:29
合計ジャッジ時間 23,277 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 WA * 16 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

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 = float("inf")
# 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
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 i in F[r]:
        l = que[i][0]
        for x in D:
            # 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 
            A = [2] * 10
            ff = []
            flag = 1
            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:
                    flag = 0
            if flag:
                # print(l, r, x, ff)
                ans[i] = min(ans[i], (r-1 + r-2 + r-3) - sum(ff) + inv(ff))
            else:
                # print(l, r, x, ff, "!")
                pass


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] == 0:
            print(0)
        elif s[l+1] * 10 + s[l] == 0:
            print(1)
        else:
            print(-1)
    else:
        if ans[i] == inf:
            print(-1)
        else:
            print(ans[i])
0