結果

問題 No.2242 Cities and Teleporters
ユーザー navel_tosnavel_tos
提出日時 2023-05-19 19:05:37
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,509 bytes
コンパイル時間 427 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 307,344 KB
最終ジャッジ日時 2024-12-18 01:02:24
合計ジャッジ時間 53,881 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
59,296 KB
testcase_01 AC 41 ms
306,188 KB
testcase_02 AC 40 ms
59,684 KB
testcase_03 AC 41 ms
307,344 KB
testcase_04 AC 41 ms
60,760 KB
testcase_05 AC 1,891 ms
186,844 KB
testcase_06 AC 1,399 ms
202,580 KB
testcase_07 AC 1,970 ms
192,312 KB
testcase_08 AC 2,474 ms
195,252 KB
testcase_09 AC 2,551 ms
192,568 KB
testcase_10 AC 2,055 ms
258,324 KB
testcase_11 AC 1,819 ms
256,268 KB
testcase_12 AC 1,810 ms
255,860 KB
testcase_13 AC 2,106 ms
258,148 KB
testcase_14 AC 2,385 ms
257,256 KB
testcase_15 AC 2,110 ms
258,800 KB
testcase_16 AC 2,284 ms
258,628 KB
testcase_17 AC 2,912 ms
258,884 KB
testcase_18 TLE -
testcase_19 AC 1,747 ms
252,868 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 1,717 ms
250,328 KB
testcase_23 TLE -
testcase_24 TLE -
testcase_25 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys; input=sys.stdin.readline
from bisect import bisect_left as bL, bisect_right as bR
f=lambda:list(map(int,input().split()))
N=int(input()); H,T=[f() for _ in range(2)]; Q=int(input())

#座標圧縮
S=set(H+T); D={j:i for i,j in enumerate(sorted(S))}
for i in range(N): H[i],T[i]=D[H[i]],D[T[i]]

#move[i]: 標高i以下のテレポーターを1回使うことで移動可能な最大の標高
P=sorted([(T[i],H[i]) for i in range(N)],reverse=True); move=[-1]*len(S); Lt=len(S)-1
for t,h in P:
    if h>t: move[h]=max(move[h],t); continue
    Lt=min(Lt,t)
    while Lt>=h: move[Lt]=t; Lt-=1
for i in range(1,len(S)): move[i]=max(move[i],move[i-1])

#DP[i][j]: 標高iから2**j回以内の移動を行うことで到達できる最大の標高(-1は移動不能)
#ここで、移動することで不利になる場合は移動しない点に注意せよ
DP=[[move[i]]+[-1]*19 for i in range(len(S))]
for j in range(1,20):
    for i in range(len(S)):
        if DP[i][j-1]==-1: continue
        DP[i][j]=max(DP[i][j-1],DP[DP[i][j-1]][j-1])

#クエリに解答
for _ in range(Q):
    A,B=f(); end=H[B-1]; now=T[A-1]; cnt=1  #初回の移動だけは例外で、T[now]に移動する
    #2**19回 ≒ 5e5回の移動でも届かないならば、到達不能と判断して良い
    if DP[H[A-1]][-1]<end: print(-1); continue
    #DP[now][j]のうち、end以下である最小のjを求め移動する
    while now<end:
        x=max(0,bL(DP[now],end)-1); cnt+=2**x; now=DP[now][x]
    print(cnt)
0