結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 12:52:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,498 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 196,220 KB
最終ジャッジ日時 2025-06-12 12:54:30
合計ジャッジ時間 6,680 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    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
    
    # Prepare sorted_h and prefix_max
    sorted_h = sorted(zip(H, T), key=lambda x: x[0])
    hs = [h for h, t in sorted_h]
    ts = [t for h, t in sorted_h]
    prefix_max = []
    current_max = -1
    for t in ts:
        if t > current_max:
            current_max = t
        prefix_max.append(current_max)
    
    # Process each query
    for A, B in queries:
        H_b = H[B]
        T_a = T[A]
        if H_b <= T_a:
            print(1)
            continue
        current_max_t = T_a
        steps = 1
        found = False
        while True:
            # Find the largest index where H <= current_max_t
            idx = bisect.bisect_right(hs, current_max_t) - 1
            if idx < 0:
                print(-1)
                break
            new_max = prefix_max[idx]
            if new_max <= current_max_t:
                print(-1)
                break
            steps +=1
            current_max_t = new_max
            if current_max_t >= H_b:
                print(steps)
                break

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