結果
問題 |
No.2242 Cities and Teleporters
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()