結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:33:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,734 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,020 KB
実行使用メモリ 194,796 KB
最終ジャッジ日時 2025-06-12 20:34:40
合計ジャッジ時間 17,990 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    
    H = list(map(int, input[ptr:ptr + N]))
    ptr += N
    
    T = list(map(int, input[ptr:ptr + N]))
    ptr += N
    
    cities = list(zip(H, T))
    cities.sort(key=lambda x: x[0])
    
    H_sorted = [h for h, t in cities]
    T_sorted = [t for h, t in cities]
    
    # Compute prefix max of T_sorted
    max_T = [0] * len(T_sorted)
    if len(T_sorted) > 0:
        max_T[0] = T_sorted[0]
        for i in range(1, len(T_sorted)):
            max_T[i] = max(max_T[i-1], T_sorted[i])
    
    Q = int(input[ptr])
    ptr += 1
    
    for _ in range(Q):
        A = int(input[ptr]) - 1
        B = int(input[ptr + 1]) - 1
        ptr += 2
        
        H_B = H[B]
        T_A = T[A]
        
        if H_B <= T_A:
            print(1)
            continue
        
        # Compute M1
        x = T_A
        idx = bisect.bisect_right(H_sorted, x) - 1
        if idx == -1:
            M1 = 0
        else:
            M1 = max_T[idx]
        
        if H_B <= M1:
            print(2)
            continue
        
        # Compute M2
        x2 = M1
        idx2 = bisect.bisect_right(H_sorted, x2) - 1
        if idx2 == -1:
            M2 = 0
        else:
            M2 = max_T[idx2]
        
        if H_B <= M2:
            print(3)
            continue
        
        # Compute M3
        x3 = M2
        idx3 = bisect.bisect_right(H_sorted, x3) - 1
        if idx3 == -1:
            M3 = 0
        else:
            M3 = max_T[idx3]
        
        if H_B <= M3:
            print(4)
            continue
        
        print(-1)

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