結果

問題 No.2242 Cities and Teleporters
ユーザー rlangevinrlangevin
提出日時 2023-11-26 12:17:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,347 bytes
コンパイル時間 336 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 182,424 KB
最終ジャッジ日時 2024-09-26 11:38:02
合計ジャッジ時間 14,926 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
54,784 KB
testcase_01 AC 39 ms
54,400 KB
testcase_02 AC 39 ms
54,272 KB
testcase_03 AC 39 ms
54,144 KB
testcase_04 AC 39 ms
54,400 KB
testcase_05 AC 2,465 ms
170,776 KB
testcase_06 AC 1,569 ms
179,276 KB
testcase_07 AC 2,497 ms
179,944 KB
testcase_08 TLE -
testcase_09 TLE -
testcase_10 AC 1,555 ms
181,468 KB
testcase_11 AC 1,119 ms
153,088 KB
testcase_12 AC 1,118 ms
153,200 KB
testcase_13 AC 1,658 ms
152,952 KB
testcase_14 AC 1,782 ms
157,252 KB
testcase_15 AC 1,453 ms
153,276 KB
testcase_16 AC 2,138 ms
156,852 KB
testcase_17 AC 2,688 ms
163,136 KB
testcase_18 AC 1,418 ms
152,624 KB
testcase_19 AC 1,009 ms
159,092 KB
testcase_20 AC 1,374 ms
149,848 KB
testcase_21 AC 1,269 ms
150,696 KB
testcase_22 AC 955 ms
164,404 KB
testcase_23 AC 996 ms
153,896 KB
testcase_24 AC 949 ms
152,760 KB
testcase_25 AC 964 ms
153,028 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = sys.stdin.readline
N = int(input())
H = list(map(int, input().split()))
T = list(map(int, input().split()))
HT = []
for i in range(N):
HT.append((-T[i], H[i], i))
HT.sort()
M = 18
dp = [[-1] * N for i in range(M)]
from bisect import *
from collections import *
inf = 10 ** 18
minv = defaultdict(lambda : inf)
L = [-inf]
for t, h, i in HT:
h = -h
ind = bisect_left(L, t)
if ind != len(L):
dp[0][i] = minv[L[ind]]
if h > L[-1]:
L.append(h)
minv[h] = i
for i in range(1, M):
for j in range(N):
if dp[i-1][j] == -1:
continue
dp[i][j] = dp[i-1][dp[i-1][j]]
def check(m, A, B):
now = A
for i in range(M):
if (m >> i) & 1:
now = dp[i][now]
if now == -1:
return 2
return T[now] >= H[B]
Q = int(input())
for _ in range(Q):
A, B = map(int, input().split())
A, B = A - 1, B - 1
if H[B] <= T[A]:
print(1)
continue
yes = N + 1
no = 0
ok = 0
while yes - no != 1:
mid = (yes + no)//2
flag = check(mid, A, B)
if flag:
yes = mid
if flag != 2:
ok = 1
else:
no = mid
if not ok:
print(-1)
else:
print(yes + 1)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0