結果
問題 | No.2242 Cities and Teleporters |
ユーザー | rlangevin |
提出日時 | 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 |
ソースコード
import sysinput = sys.stdin.readlineN = 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 = 18dp = [[-1] * N for i in range(M)]from bisect import *from collections import *inf = 10 ** 18minv = defaultdict(lambda : inf)L = [-inf]for t, h, i in HT:h = -hind = bisect_left(L, t)if ind != len(L):dp[0][i] = minv[L[ind]]if h > L[-1]:L.append(h)minv[h] = ifor i in range(1, M):for j in range(N):if dp[i-1][j] == -1:continuedp[i][j] = dp[i-1][dp[i-1][j]]def check(m, A, B):now = Afor i in range(M):if (m >> i) & 1:now = dp[i][now]if now == -1:return 2return T[now] >= H[B]Q = int(input())for _ in range(Q):A, B = map(int, input().split())A, B = A - 1, B - 1if H[B] <= T[A]:print(1)continueyes = N + 1no = 0ok = 0while yes - no != 1:mid = (yes + no)//2flag = check(mid, A, B)if flag:yes = midif flag != 2:ok = 1else:no = midif not ok:print(-1)else:print(yes + 1)