結果
| 問題 |
No.1568 Sushi
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-09 21:01:51 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,498 bytes |
| コンパイル時間 | 284 ms |
| コンパイル使用メモリ | 82,344 KB |
| 実行使用メモリ | 93,624 KB |
| 最終ジャッジ日時 | 2025-04-09 21:03:42 |
| 合計ジャッジ時間 | 6,563 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | TLE * 1 -- * 24 |
ソースコード
import bisect
L, N, Q = map(int, input().split())
A = list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(Q)]
# Precompute preD and directions
preD = [0]
directions = [1] # directions[0] is the initial direction before any events
current_direction = 1
for i in range(N):
if i == 0:
delta = A[i]
else:
delta = A[i] - A[i-1]
preD.append(preD[-1] + current_direction * delta)
current_direction *= -1
directions.append(current_direction)
def compute_D(s):
if not A:
return s
j = bisect.bisect_right(A, s) - 1
if j < 0:
# All A[i] > s, so before any event
return 1 * s # since initial direction is 1 (preD[0] =0)
a_prev = A[j]
direction = directions[j+1]
displacement = preD[j+1] + direction * (s - a_prev)
return displacement
def find_intervals(t_start, t_end):
intervals = []
if not A:
if t_start < t_end:
intervals.append((t_start, t_end))
return intervals
start_idx = bisect.bisect_left(A, t_start)
end_idx = bisect.bisect_right(A, t_end)
# Initial interval [t_start, min(A[start_idx], t_end)] if start_idx < len(A)
if start_idx > 0:
prev_a = A[start_idx-1]
else:
prev_a = 0
current_a = A[start_idx] if start_idx < len(A) else t_end + 1
if start_idx == 0 and prev_a ==0 and current_a > t_start:
new_a_start = t_start
new_a_end = min(current_a, t_end)
if new_a_start < new_a_end:
intervals.append((new_a_start, new_a_end))
else:
if start_idx < len(A) and current_a > t_start:
new_a_start = t_start
new_a_end = min(current_a, t_end)
if new_a_start < new_a_end:
intervals.append((new_a_start, new_a_end))
# Process middle intervals
for i in range(start_idx, min(end_idx, len(A))):
a_start = A[i]
a_end = A[i+1] if (i+1 < len(A)) else t_end + 1
a_start_clamped = max(a_start, t_start)
a_end_clamped = min(a_end, t_end)
if a_start_clamped < a_end_clamped:
intervals.append((a_start_clamped, a_end_clamped))
# Process the last interval after end_idx-1
if end_idx <= len(A):
if end_idx ==0:
a_last_event = 0
else:
a_last_event = A[end_idx-1]
if a_last_event < t_end:
new_start = max(a_last_event, t_start)
if new_start < t_end:
intervals.append((new_start, t_end))
else:
a_last_event = A[-1]
if a_last_event < t_end:
new_start = max(a_last_event, t_start)
if new_start < t_end:
intervals.append((new_start, t_end))
return intervals
def check_condition(s, x, t_i, L):
D_s = compute_D(s)
target = (D_s - x) % L
intervals = find_intervals(t_i, s)
for a_start, a_end in intervals:
if a_start >= a_end:
continue
j = bisect.bisect_right(A, a_start) -1
if j < 0:
# Before any events
a_prev_event = 0
dir_j_plus_1 = directions[0]
displacement_start = dir_j_plus_1 * (a_start - a_prev_event)
else:
a_prev_event = A[j]
dir_j_plus_1 = directions[j+1] if (j+1) < len(directions) else directions[-1]
displacement_start = preD[j+1] + dir_j_plus_1 * (a_start - a_prev_event)
len_interval = a_end - a_start
if len_interval >= L:
return True
direction = dir_j_plus_1
S = displacement_start % L
E = (displacement_start + direction * (a_end - a_start - 1)) % L
if direction ==1:
if S <= E:
if S <= target <= E:
return True
else:
if target >= S or target <= E:
return True
else:
if E <= S:
if E <= target <= S:
return True
else:
if target >= E or target <= S:
return True
return False
prev_answer = 0
for B, C in queries:
x_i = (B + prev_answer) % L
t_i = (C + prev_answer) % (10**15)
low = t_i
high = t_i + L
answer = -1
while low <= high:
mid = (low + high) // 2
if check_condition(mid, x_i, t_i, L):
answer = mid - t_i
high = mid - 1
else:
low = mid + 1
print(answer)
prev_answer = answer