結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:11:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,502 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 201,452 KB
最終ジャッジ日時 2025-04-15 22:13:00
合計ジャッジ時間 6,063 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0

    N = int(data[ptr])
    ptr += 1

    H = list(map(int, data[ptr:ptr+N]))
    ptr += N

    T = list(map(int, data[ptr:ptr+N]))
    ptr += N

    Q = int(data[ptr])
    ptr += 1

    queries = []
    for _ in range(Q):
        A = int(data[ptr]) - 1
        B = int(data[ptr+1]) - 1
        queries.append((A, B))
        ptr += 2

    # Preprocess sorted_H and related arrays
    sorted_nodes = sorted(enumerate(H), key=lambda x: x[1])
    sorted_indices = [idx for idx, h in sorted_nodes]
    sorted_H = [h for idx, h in sorted_nodes]
    sorted_T = [T[idx] for idx in sorted_indices]

    n = len(sorted_H)
    max_val = [0] * n
    max_idx = [0] * n
    second_max = [0] * n

    max_val[0] = sorted_T[0]
    max_idx[0] = 0
    second_max[0] = -1

    for i in range(1, n):
        current_T = sorted_T[i]
        if current_T > max_val[i-1]:
            max_val[i] = current_T
            max_idx[i] = i
            second_max[i] = max_val[i-1]
        else:
            max_val[i] = max_val[i-1]
            max_idx[i] = max_idx[i-1]
            if current_T > second_max[i-1]:
                second_max[i] = current_T
            else:
                second_max[i] = second_max[i-1]

    # Create a dictionary to map original index to sorted index
    pos_dict = {sorted_indices[i]: i for i in range(n)}

    # Precompute global maximum T
    global_max_T = max(T)

    # Process each query
    output = []
    for A, B in queries:
        H_B = H[B]
        if H_B > global_max_T:
            output.append("-1")
            continue

        T_A = T[A]
        if H_B <= T_A:
            if A == B:
                output.append("-1")
                continue
            # Find pos in sorted_H where H_j <= T_A
            pos = bisect.bisect_right(sorted_H, T_A) - 1
            if pos < 0:
                output.append("-1")
                continue
            # Check if B is in the first pos+1 nodes and not A
            B_sorted_pos = pos_dict[B]
            if B_sorted_pos <= pos and sorted_H[B_sorted_pos] <= T_A and B != A:
                output.append("1")
            else:
                output.append("-1")
            continue

        # Now handle the case where H_B > T_A
        # Compute new_max_0 (step 1's max T)
        pos = bisect.bisect_right(sorted_H, T_A) - 1
        if pos < 0:
            new_max = 0
        else:
            A_sorted_pos = pos_dict[A]
            if A_sorted_pos > pos:
                new_max = max_val[pos]
            else:
                if max_idx[pos] == A_sorted_pos:
                    new_max = second_max[pos]
                else:
                    new_max = max_val[pos]
        steps = 1
        current_max = new_max
        if current_max >= H_B:
            output.append(str(steps + 1))
            continue

        prev_max = -1
        while current_max != prev_max and current_max < H_B:
            prev_max = current_max
            pos = bisect.bisect_right(sorted_H, current_max) - 1
            if pos >= 0:
                new_max = max_val[pos]
            else:
                new_max = 0
            current_max = new_max
            steps += 1
            if current_max >= H_B:
                break

        if current_max >= H_B:
            output.append(str(steps + 1))
        else:
            output.append("-1")

    print('\n'.join(output))

if __name__ == "__main__":
    main()
0