結果

問題 No.2242 Cities and Teleporters
ユーザー 👑 timitimi
提出日時 2023-03-24 14:13:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 834 bytes
コンパイル時間 1,669 ms
コンパイル使用メモリ 81,272 KB
実行使用メモリ 194,108 KB
最終ジャッジ日時 2023-10-18 20:26:33
合計ジャッジ時間 44,195 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
53,564 KB
testcase_01 AC 39 ms
53,564 KB
testcase_02 AC 39 ms
53,564 KB
testcase_03 AC 39 ms
53,564 KB
testcase_04 AC 40 ms
53,564 KB
testcase_05 AC 1,862 ms
184,352 KB
testcase_06 AC 1,188 ms
190,132 KB
testcase_07 AC 1,751 ms
193,404 KB
testcase_08 AC 1,964 ms
194,056 KB
testcase_09 AC 1,849 ms
193,392 KB
testcase_10 AC 1,460 ms
193,628 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 1,738 ms
189,260 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
権限があれば一括ダウンロードができます

ソースコード

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