結果

問題 No.2242 Cities and Teleporters
ユーザー navel_tosnavel_tos
提出日時 2023-05-19 20:07:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,603 ms / 3,000 ms
コード長 3,153 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 257,692 KB
最終ジャッジ日時 2024-05-10 04:30:27
合計ジャッジ時間 26,518 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
52,352 KB
testcase_01 AC 36 ms
52,096 KB
testcase_02 AC 39 ms
52,224 KB
testcase_03 AC 40 ms
52,224 KB
testcase_04 AC 41 ms
51,840 KB
testcase_05 AC 1,454 ms
187,028 KB
testcase_06 AC 918 ms
202,832 KB
testcase_07 AC 1,360 ms
195,024 KB
testcase_08 AC 1,654 ms
194,884 KB
testcase_09 AC 1,655 ms
194,760 KB
testcase_10 AC 1,702 ms
257,692 KB
testcase_11 AC 1,612 ms
255,896 KB
testcase_12 AC 1,523 ms
255,480 KB
testcase_13 AC 1,781 ms
256,116 KB
testcase_14 AC 1,821 ms
255,556 KB
testcase_15 AC 2,603 ms
255,276 KB
testcase_16 AC 1,898 ms
255,952 KB
testcase_17 AC 2,032 ms
255,244 KB
testcase_18 AC 1,614 ms
255,172 KB
testcase_19 AC 1,474 ms
253,696 KB
testcase_20 AC 1,690 ms
250,448 KB
testcase_21 AC 1,693 ms
252,268 KB
testcase_22 AC 1,476 ms
250,528 KB
testcase_23 AC 1,511 ms
254,772 KB
testcase_24 AC 1,516 ms
255,208 KB
testcase_25 AC 1,555 ms
255,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder380D Cities and Teleporters

'''
下方向には自由に移動できるが、上方向への移動は限られる、というのが重要かな。
上昇方向のテレポーターのみを抽出して考えよう。

各町から最高の標高に移動する方法、を考えればよいのか。
とりあえず標高は座圧しよう、4*10**5通りまで減らせる。

事前の各標高に対して「この町から移動できる最大の標高」を記録しよう。
各町に対して、ではない点に注意。
後はダブリングかな。2**19 = 5.2e5 なので、ダブリング回数は20回で済む。
DP[i][j]: 町iから2**j回の移動で到達できる最大の標高
として、jが小さい順に埋めればよい。そのためには事前準備が必要か。大変だな。

テレポーターの移動先を降順ソートして、貪欲にあてはめればよいのかな。
移動ルールが Hi→Ti だったよな。
(Ti,Hi)の順にソートして、Tiを降順に見てゆく。
Hi> Ti は無視する。
Hi<=Ti で、Tiが固有値なら、区間[Hi,Ti]はTiにしてよい。
       Tiが同率なら、Hiが大きい順に見てゆけばOK。
「この標高まで更新した」のカーソルLtを保持しながら見れば大丈夫かな。

TLEする。でもよく考えたら毎回bisectするの計算量の無駄だな？
ダブリング先で移動回数が増えることは絶対にないのだから、カーソルは一方向的に動かしてよい。
'''
import sys; input=sys.stdin.readline
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  #1回目の移動直後から考える
    #2**19回 ≒ 5e5回の移動でも届かないならば、到達不能と判断して良い
    if now>=end: print(1); continue  #処理順を入れ替え
    if DP[now][-1]<end: print(-1); continue
    #DP[now][j]のうち、end以下である最小のjを求め移動する
    for Rt in range(19,-1,-1):
        if DP[now][Rt]>=end: continue
        cnt+=2**Rt; now=DP[now][Rt]
    if now<end: cnt+=1  #あと1回の移動でちょうどendに到達する場合を例外処理
    print(cnt)
0