結果
問題 |
No.2242 Cities and Teleporters
|
ユーザー |
![]() |
提出日時 | 2025-04-15 22:11:02 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,466 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 82,016 KB |
実行使用メモリ | 53,944 KB |
最終ジャッジ日時 | 2025-04-15 22:12:39 |
合計ジャッジ時間 | 6,726 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 5 TLE * 1 -- * 20 |
ソースコード
import sys import bisect def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 H = list(map(int, input[ptr:ptr+N])) ptr += N T = list(map(int, input[ptr:ptr+N])) ptr += N Q = int(input[ptr]) ptr += 1 queries = [] for _ in range(Q): A = int(input[ptr])-1 B = int(input[ptr+1])-1 queries.append((A, B)) ptr += 2 sorted_h = sorted(zip(H, T), key=lambda x: x[0]) H_sorted = [x[0] for x in sorted_h] T_sorted = [x[1] for x in sorted_h] max1 = [] count_max = [] max2 = [] current_max = -float('inf') current_count = 0 current_max2 = -float('inf') for t in T_sorted: if t > current_max: current_max2 = current_max current_max = t current_count = 1 elif t == current_max: current_count += 1 else: if t > current_max2: current_max2 = t max1.append(current_max) count_max.append(current_count) max2.append(current_max2) for A, B in queries: H_B = H[B] T_A = T[A] if H_B <= T_A: print(1) continue i = bisect.bisect_right(H_sorted, T_A) - 1 if i < 0: print(-1) continue max_all = max1[i] count = count_max[i] if H[A] <= T_A: if T[A] == max_all: if count > 1: new_max = max_all else: new_max = max2[i] if i >= 0 else -float('inf') else: new_max = max_all else: new_max = max_all if new_max <= T_A: print(-1) continue current_max_val = new_max step_count = 1 if current_max_val >= H_B: print(2) continue while True: i_new = bisect.bisect_right(H_sorted, current_max_val) - 1 if i_new < 0: new_max_val = -float('inf') else: new_max_val = max1[i_new] if new_max_val == current_max_val: break step_count += 1 current_max_val = new_max_val if current_max_val >= H_B: break if current_max_val >= H_B: print(step_count + 1) else: print(-1) if __name__ == "__main__": main()