結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:02:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,837 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 198,260 KB
最終ジャッジ日時 2025-06-12 18:02:39
合計ジャッジ時間 8,444 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    # Sort cities by H, then by T (though T's order doesn't matter for sorting)
    cities = sorted(zip(H, T), key=lambda x: x[0])
    sorted_H = [h for h, t in cities]
    sorted_T = [t for h, t in cities]
    
    # Precompute max_T_prefix
    max_T_prefix = []
    current_max = 0
    for t in sorted_T:
        current_max = max(current_max, t)
        max_T_prefix.append(current_max)
    
    q = int(data[ptr])
    ptr += 1
    
    output = []
    for _ in range(q):
        A = int(data[ptr]) - 1  # Convert to 0-based index
        B = int(data[ptr + 1]) - 1
        ptr += 2
        
        H_B = H[B]
        T_A = T[A]
        
        if H_B <= T_A:
            output.append('1')
            continue
        
        current_M = T_A
        if current_M >= H_B:
            output.append('1')
            continue
        
        prev_M = current_M
        steps_needed = 0
        found = False
        while True:
            steps_needed += 1
            # Find the largest index where H <= prev_M
            idx = bisect.bisect_right(sorted_H, prev_M) - 1
            if idx >= 0:
                next_M = max_T_prefix[idx]
            else:
                next_M = 0
            
            if next_M >= H_B:
                output.append(str(steps_needed + 1))
                found = True
                break
            if next_M == prev_M:
                output.append('-1')
                found = True
                break
            prev_M = next_M
        
    print('\n'.join(output))

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