結果

問題 No.2242 Cities and Teleporters
ユーザー timi
提出日時 2023-03-24 14:13:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 834 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 81,848 KB
実行使用メモリ 194,852 KB
最終ジャッジ日時 2024-09-18 16:25:07
合計ジャッジ時間 36,334 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

N=int(input())
H=list(map(int, input().split()))
T=list(map(int, input().split()))
A=[(0,0,0)]
for i in range(N):
  A.append((H[i],T[i],i+1))
A=sorted(A)
D={}
for i in range(N+1):
  D[A[i][2]]=i

HH=[0]+H
HH=sorted(HH)
import bisect
a=len(A)
b=a.bit_length()
dp=[[0]*a for _ in range(b)]
for i in range(a):
  if i==0:
    dp[0][0]=0
    h=0
  else:
    bb=A[i][1]
    h=max(h,bb)
    d=bisect.bisect_right(HH,h)-1
    dp[0][i]=max(i,d)
    
for k in range(1,b):
  for i in range(a):
    dp[k][i] = dp[k-1][dp[k-1][i]]

Q=int(input())
for _ in range(Q):
  x,y=map(int, input().split())
  if T[x-1]>=H[y-1]:
    print(1)
    continue
  s,g=D[x],D[y]
  c=0
  for i in range(b-1,-1,-1):
    if dp[i][s]<g:
      s=dp[i][s]
      c+=2**i
  if s!=g:
    c+=1
  s=dp[0][s]
  if s!=g:
    c+=1
  if c>=2**b:
    print(-1)
  else:
    print(c)
0