結果
| 問題 | No.3244 Range Multiple of 8 Query |
| コンテスト | |
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2026-01-05 01:09:03 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,537 bytes |
| 記録 | |
| コンパイル時間 | 379 ms |
| コンパイル使用メモリ | 82,568 KB |
| 実行使用メモリ | 280,304 KB |
| 最終ジャッジ日時 | 2026-01-05 01:09:16 |
| 合計ジャッジ時間 | 10,924 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 17 TLE * 1 -- * 22 |
ソースコード
# https://yukicoder.me/problems/no/3244
class SegmentTree:
"""
非再帰版セグメント木。
更新は「加法」、取得は「最大値」のもの限定。
"""
def __init__(self, init_array):
n = 1
while n < len(init_array):
n *= 2
self.size = n
self.array = [[-1] * 10 for _ in range(2 * self.size)]
for i, a in enumerate(init_array):
self.array[self.size + i][int(a)] = i
end_index = self.size
start_index = end_index // 2
while start_index >= 1:
for i in range(start_index, end_index):
self._op(self.array[i], self.array[2 * i], self.array[2 * i + 1])
end_index = start_index
start_index = end_index // 2
def _op(self, array, left, right):
for d in range(1, 10):
array[d] = max(left[d], right[d])
def get_latest_index(self, l, r):
L = self.size + l; R = self.size + r
# 2. 区間[l, r)の最大値を求める
s = [-1] * 10
while L < R:
if R & 1:
R -= 1
self._op(s, s, self.array[R])
if L & 1:
self._op(s, s, self.array[L])
L += 1
L >>= 1; R >>= 1
return s
def get_last_three_values():
array = []
for i in range(1000):
if i % 8 == 0:
i0 = 1000 + i
str_i = str(i0)
is_ok = True
for s in str_i[-3:]:
if s == "0":
is_ok = False
if is_ok:
array.append(str_i[-3:])
return array
def solve_length1(s):
if int(s) == 8:
print(0)
else:
print(-1)
def solve_length2(s):
# ひっくり返さない場合
if int(s) % 8 == 0:
print(0)
else:
s1 = s[1] + s[0]
if int(s1) % 8 == 0:
print(1)
else:
print(-1)
def solve_length3(seg_tree, S, last_three_values, l, r):
base_s = S[(r - 2):(r + 1)]
answer = float("inf")
for ideal_value in last_three_values:
ans = 0
target_range = [(l, r, 0)]
target_index = -1
used_index = set()
is_ok = True
for ideal_digit in reversed(ideal_value):
b = base_s[target_index]
if ideal_digit == b:
used_index.add(r + 1 + target_index)
while (r + 1 + target_index) in used_index:
target_index -= 1
new_target_range = []
for l0, r0, _ in target_range:
appendable = True
for d in used_index:
if not (l0 <= d <= r0):
continue
appendable = False
if l0 == d and r0 == d:
break
if l0 == d:
new_target_range.append((l0 + 1, r0))
elif r0 == d:
new_target_range.append((l0, r0 - 1))
else:
new_target_range.append((l0, d - 1))
new_target_range.append((d + 1, r0))
if appendable:
new_target_range.append((l0, r0))
new_target_range.sort(key=lambda x : x[0])
weight = 0
target_range.clear()
for l0, r0 in reversed(new_target_range):
target_range.append((l0, r0, weight))
weight += 1
else:
rx = r + 1 + target_index
ind = -1
weight = 0
for l0, r0, w in target_range:
l1 = l0
if r0 == rx:
r1 = r0 - 1
else:
r1 = r0
if l1 <= r1:
latest_index = seg_tree.get_latest_index(l1, r1 +1)
if latest_index[int(ideal_digit)] != -1:
ind = latest_index[int(ideal_digit)]
weight = w
break
if ind == -1:
is_ok = False
break
else:
ans += r + 1 + target_index - ind - weight
used_index.add(ind)
new_target_range = []
for l0, r0, _ in target_range:
appendable = True
for d in used_index:
if not (l0 <= d <= r0):
continue
appendable = False
if l0 == d and r0 == d:
break
if l0 == d:
new_target_range.append((l0 + 1, r0))
elif r0 == d:
new_target_range.append((l0, r0 - 1))
else:
new_target_range.append((l0, d - 1))
new_target_range.append((d + 1, r0))
if appendable:
new_target_range.append((l0, r0))
new_target_range.sort(key=lambda x : x[0])
weight = 0
target_range.clear()
for l0, r0 in reversed(new_target_range):
target_range.append((l0, r0, weight))
weight += 1
if is_ok:
answer = min(answer, ans)
if answer == float("inf"):
print(-1)
else:
print(answer)
def main():
N, Q = map(int, input().split())
S = input()
lr = []
for _ in range(Q):
l, r = map(int, input().split())
lr.append((l - 1, r - 1))
# 3桁以上の場合、下３桁が以下のようになっていればOK
last_three_values = get_last_three_values()
seg_tree = SegmentTree([s for s in S])
for l, r in lr:
if r - l == 0:
# 長さ1
solve_length1(S[l])
elif r - l == 1:
# 長さ2
solve_length2(S[l:(r + 1)])
else:
# 長さ3以上
solve_length3(seg_tree, S, last_three_values, l, r)
if __name__ == "__main__":
main()