結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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
0