結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:14:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,830 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 81,552 KB
実行使用メモリ 53,996 KB
最終ジャッジ日時 2025-04-15 22:16:25
合計ジャッジ時間 7,059 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    # Create a list of (H_i, T_i) and sort by H_i
    cities = sorted(zip(H, T), key=lambda x: x[0])
    sorted_H = [x[0] for x in cities]
    sorted_T = [x[1] for x in cities]
    
    # Precompute prefix max array
    prefix_max = []
    current_max = -1
    for t in sorted_T:
        if t > current_max:
            current_max = t
        prefix_max.append(current_max)
    
    # Function to compute next_T given current_T
    def compute_next_T(T_prev):
        # Find the largest index where sorted_H <= T_prev
        idx = bisect.bisect_right(sorted_H, T_prev) - 1
        if idx < 0:
            return 0  # No cities available
        return prefix_max[idx]
    
    Q = int(data[ptr])
    ptr += 1
    for _ in range(Q):
        A = int(data[ptr]) - 1  # 0-based
        B = int(data[ptr+1]) - 1
        ptr += 2
        
        H_B = H[B]
        T_A = T[A]
        
        if H_B <= T_A:
            print(1)
            continue
        
        # Compute T_final
        current_T = T_A
        prev_T = -1
        while True:
            next_T = compute_next_T(current_T)
            if next_T == current_T:
                break
            prev_T = current_T
            current_T = next_T
        T_final = current_T
        
        if H_B > T_final:
            print(-1)
            continue
        
        # Compute minimal steps
        current_T = T_A
        steps = 1
        while current_T < H_B:
            current_T = compute_next_T(current_T)
            steps += 1
        print(steps)

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