結果
問題 | No.2242 Cities and Teleporters |
ユーザー |
![]() |
提出日時 | 2023-03-10 22:27:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,892 ms / 3,000 ms |
コード長 | 1,187 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,316 KB |
実行使用メモリ | 169,352 KB |
最終ジャッジ日時 | 2024-09-18 04:39:11 |
合計ジャッジ時間 | 34,988 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
import sysinput = sys.stdin.readlinefrom collections import *from bisect import *N = int(input())H = list(map(int, input().split()))T = list(map(int, input().split()))HTI = [(H[i], T[i], i) for i in range(N)]HTI.sort()H = [Hi for Hi, _, _ in HTI]T = [Ti for _, Ti, _ in HTI]idx = [-1]*Nfor i in range(N):idx[HTI[i][2]] = ito = [0]*(N+1)for v in range(N):to[v+1] = bisect_right(H, T[v])dp = [[0]*(N+1) for _ in range(30)]for v in range(1, N+1):dp[0][v] = max(dp[0][v-1], to[v])for i in range(1, 30):for v in range(N+1):dp[i][v] = dp[i-1][dp[i-1][v]]Q = int(input())for _ in range(Q):A, B = map(int, input().split())A = idx[A-1]+1B = idx[B-1]+1v = to[A]if B<=v:print(1)else:ok, ng = N+10, 0while abs(ok-ng)>1:mid = (ok+ng)//2now = vfor i in range(25):if (mid>>i)&1:now = dp[i][now]if B<=now:ok = midelse:ng = midif ok>N:print(-1)else:print(ok+1)