結果
問題 |
No.2242 Cities and Teleporters
|
ユーザー |
![]() |
提出日時 | 2025-04-15 22:09:25 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,718 bytes |
コンパイル時間 | 303 ms |
コンパイル使用メモリ | 81,808 KB |
実行使用メモリ | 53,612 KB |
最終ジャッジ日時 | 2025-04-15 22:11:00 |
合計ジャッジ時間 | 6,395 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 5 TLE * 1 -- * 20 |
ソースコード
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()