結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:31:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,505 bytes
コンパイル時間 282 ms
コンパイル使用メモリ 82,088 KB
実行使用メモリ 195,892 KB
最終ジャッジ日時 2025-03-31 17:32:45
合計ジャッジ時間 8,534 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    data = sys.stdin.read().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
    
    # Sort cities by their height
    sorted_HT = sorted(zip(H, T), key=lambda x: x[0])
    sorted_H = [ht[0] for ht in sorted_HT]
    sorted_T = [ht[1] for ht in sorted_HT]
    
    # Compute prefix maximum array for T values
    prefix_max = [0] * N
    prefix_max[0] = sorted_T[0]
    for i in range(1, N):
        prefix_max[i] = max(prefix_max[i-1], sorted_T[i])
    
    output = []
    for A, B in queries:
        h_b = H[B]
        t_a = T[A]
        if h_b <= t_a:
            output.append('1')
            continue
        current_m = t_a
        steps = 1
        while True:
            idx = bisect.bisect_right(sorted_H, current_m) - 1
            if idx < 0:
                next_m = -1
            else:
                next_m = prefix_max[idx]
            if next_m == current_m:
                output.append('-1')
                break
            steps += 1
            current_m = next_m
            if current_m >= h_b:
                output.append(str(steps))
                break
    
    print('\n'.join(output))

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