結果
問題 |
No.2242 Cities and Teleporters
|
ユーザー |
![]() |
提出日時 | 2025-04-15 22:14:36 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,830 bytes |
コンパイル時間 | 226 ms |
コンパイル使用メモリ | 81,552 KB |
実行使用メモリ | 53,996 KB |
最終ジャッジ日時 | 2025-04-15 22:16:25 |
合計ジャッジ時間 | 7,059 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 # Create a list of (H_i, T_i) and sort by H_i cities = sorted(zip(H, T), key=lambda x: x[0]) sorted_H = [x[0] for x in cities] sorted_T = [x[1] for x in cities] # Precompute prefix max array prefix_max = [] current_max = -1 for t in sorted_T: if t > current_max: current_max = t prefix_max.append(current_max) # Function to compute next_T given current_T def compute_next_T(T_prev): # Find the largest index where sorted_H <= T_prev idx = bisect.bisect_right(sorted_H, T_prev) - 1 if idx < 0: return 0 # No cities available return prefix_max[idx] Q = int(data[ptr]) ptr += 1 for _ in range(Q): A = int(data[ptr]) - 1 # 0-based B = int(data[ptr+1]) - 1 ptr += 2 H_B = H[B] T_A = T[A] if H_B <= T_A: print(1) continue # Compute T_final current_T = T_A prev_T = -1 while True: next_T = compute_next_T(current_T) if next_T == current_T: break prev_T = current_T current_T = next_T T_final = current_T if H_B > T_final: print(-1) continue # Compute minimal steps current_T = T_A steps = 1 while current_T < H_B: current_T = compute_next_T(current_T) steps += 1 print(steps) if __name__ == "__main__": main()