結果
問題 |
No.2242 Cities and Teleporters
|
ユーザー |
|
提出日時 | 2024-04-28 14:55:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,097 ms / 3,000 ms |
コード長 | 934 bytes |
コンパイル時間 | 329 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 245,700 KB |
最終ジャッジ日時 | 2024-11-17 07:39:55 |
合計ジャッジ時間 | 23,952 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
import sys input = sys.stdin.readline n = int(input()) H = list(map(int, input().split())) T = list(map(int, input().split())) X = H + T X = sorted(set(X)) dic = {X[i]: i for i in range(len(X))} H = [dic[h] for h in H] T = [dic[t] for t in T] le = len(X) m = 20 nex = [[i for i in range(le)] for _ in range(m)] for h, t in zip(H, T): nex[0][h] = max(nex[0][h], t) for i in range(1, le): nex[0][i] = max(nex[0][i], nex[0][i - 1]) for i in range(1, m): for j in range(le): nex[i][j] = nex[i - 1][nex[i - 1][j]] Q = int(input()) for _ in range(Q): a, b = map(int, input().split()) a -= 1 b -= 1 if T[a] >= H[b]: print(1) continue ans = 1 t = T[a] for i in range(m - 1, -1, -1): nt = nex[i][t] if nt < H[b]: t = nt ans += 1 << i ans += 1 nt = nex[0][t] if nt >= H[b]: print(ans) else: print(-1)