結果
問題 |
No.2242 Cities and Teleporters
|
ユーザー |
![]() |
提出日時 | 2025-04-15 22:11:25 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,502 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 201,452 KB |
最終ジャッジ日時 | 2025-04-15 22:13:00 |
合計ジャッジ時間 | 6,063 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 # Preprocess sorted_H and related arrays sorted_nodes = sorted(enumerate(H), key=lambda x: x[1]) sorted_indices = [idx for idx, h in sorted_nodes] sorted_H = [h for idx, h in sorted_nodes] sorted_T = [T[idx] for idx in sorted_indices] n = len(sorted_H) max_val = [0] * n max_idx = [0] * n second_max = [0] * n max_val[0] = sorted_T[0] max_idx[0] = 0 second_max[0] = -1 for i in range(1, n): current_T = sorted_T[i] if current_T > max_val[i-1]: max_val[i] = current_T max_idx[i] = i second_max[i] = max_val[i-1] else: max_val[i] = max_val[i-1] max_idx[i] = max_idx[i-1] if current_T > second_max[i-1]: second_max[i] = current_T else: second_max[i] = second_max[i-1] # Create a dictionary to map original index to sorted index pos_dict = {sorted_indices[i]: i for i in range(n)} # Precompute global maximum T global_max_T = max(T) # Process each query output = [] for A, B in queries: H_B = H[B] if H_B > global_max_T: output.append("-1") continue T_A = T[A] if H_B <= T_A: if A == B: output.append("-1") continue # Find pos in sorted_H where H_j <= T_A pos = bisect.bisect_right(sorted_H, T_A) - 1 if pos < 0: output.append("-1") continue # Check if B is in the first pos+1 nodes and not A B_sorted_pos = pos_dict[B] if B_sorted_pos <= pos and sorted_H[B_sorted_pos] <= T_A and B != A: output.append("1") else: output.append("-1") continue # Now handle the case where H_B > T_A # Compute new_max_0 (step 1's max T) pos = bisect.bisect_right(sorted_H, T_A) - 1 if pos < 0: new_max = 0 else: A_sorted_pos = pos_dict[A] if A_sorted_pos > pos: new_max = max_val[pos] else: if max_idx[pos] == A_sorted_pos: new_max = second_max[pos] else: new_max = max_val[pos] steps = 1 current_max = new_max if current_max >= H_B: output.append(str(steps + 1)) continue prev_max = -1 while current_max != prev_max and current_max < H_B: prev_max = current_max pos = bisect.bisect_right(sorted_H, current_max) - 1 if pos >= 0: new_max = max_val[pos] else: new_max = 0 current_max = new_max steps += 1 if current_max >= H_B: break if current_max >= H_B: output.append(str(steps + 1)) else: output.append("-1") print('\n'.join(output)) if __name__ == "__main__": main()