結果

問題 No.2242 Cities and Teleporters
ユーザー timitimi
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,096 KB
testcase_01 AC 37 ms
52,480 KB
testcase_02 AC 40 ms
52,864 KB
testcase_03 AC 39 ms
52,396 KB
testcase_04 AC 37 ms
53,152 KB
testcase_05 AC 1,623 ms
186,236 KB
testcase_06 AC 1,072 ms
190,604 KB
testcase_07 AC 1,535 ms
193,784 KB
testcase_08 AC 1,770 ms
194,480 KB
testcase_09 AC 1,546 ms
194,084 KB
testcase_10 AC 1,413 ms
194,376 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,452 ms
189,656 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