結果

問題 No.2242 Cities and Teleporters
ユーザー lam6er
提出日時 2025-04-15 22:14:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,718 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 81,848 KB
実行使用メモリ 195,728 KB
最終ジャッジ日時 2025-04-15 22:15:36
合計ジャッジ時間 6,265 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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
    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 T
    cities = list(zip(H, T))
    cities.sort()
    sorted_H = [h for h, t in cities]
    sorted_T = [t for h, t in 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])
    
    # Process queries
    output = []
    for A, B in queries:
        required_H = H[B]
        Ta = T[A]
        if required_H <= Ta and A != B:
            output.append("1")
            continue
        
        current_max = Ta
        steps = 0
        found = False
        while True:
            # Find the largest H <= current_max
            idx = bisect.bisect_right(sorted_H, current_max) -1
            if idx >=0:
                next_max = prefix_max_T[idx]
            else:
                next_max = 0
            
            if next_max > current_max:
                steps +=1
                current_max = next_max
                if current_max >= required_H:
                    found = True
                    break
            else:
                break
        
        if found:
            output.append(str(steps +1))
        else:
            output.append("-1")
    
    print('\n'.join(output))

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