結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:02:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,685 bytes
コンパイル時間 446 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 198,216 KB
最終ジャッジ日時 2025-06-12 18:02:46
合計ジャッジ時間 6,432 ms
ジャッジサーバーID
（参考情報） 		judge2 / 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
    
    # Prepare sorted cities and prefix max T
    sorted_cities = sorted(zip(H, T), key=lambda x: x[0])
    sorted_H = [h for h, t in sorted_cities]
    sorted_T = [t for h, t in sorted_cities]
    prefix_max_T = [0] * n
    prefix_max_T[0] = sorted_T[0]
    for i in range(1, n):
        prefix_max_T[i] = max(prefix_max_T[i-1], sorted_T[i])
    
    q = int(data[ptr])
    ptr += 1
    results = []
    for _ in range(q):
        A = int(data[ptr]) - 1
        B = int(data[ptr+1]) - 1
        ptr += 2
        
        if A == B:
            results.append(-1)
            continue
        
        H_B = H[B]
        T_A = T[A]
        
        if H_B <= T_A:
            results.append(1)
        else:
            current_max = T_A
            steps = 0
            found = False
            while True:
                # Find next_max
                idx = bisect.bisect_right(sorted_H, current_max) - 1
                if idx < 0:
                    next_max = 0
                else:
                    next_max = prefix_max_T[idx]
                
                if next_max == current_max:
                    results.append(-1)
                    break
                steps += 1
                if next_max >= H_B:
                    results.append(steps + 1)
                    break
                current_max = next_max
    
    print('\n'.join(map(str, results)))

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