結果
問題 | No.2242 Cities and Teleporters |
ユーザー | shotoyoo |
提出日時 | 2023-03-10 22:42:47 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,807 bytes |
コンパイル時間 | 939 ms |
コンパイル使用メモリ | 81,720 KB |
実行使用メモリ | 162,948 KB |
最終ジャッジ日時 | 2023-10-18 08:23:40 |
合計ジャッジ時間 | 28,064 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
56,076 KB |
testcase_01 | AC | 42 ms
56,076 KB |
testcase_02 | AC | 42 ms
56,076 KB |
testcase_03 | AC | 43 ms
56,076 KB |
testcase_04 | WA | - |
testcase_05 | AC | 1,355 ms
162,948 KB |
testcase_06 | AC | 854 ms
154,004 KB |
testcase_07 | AC | 1,278 ms
160,004 KB |
testcase_08 | AC | 1,231 ms
159,980 KB |
testcase_09 | AC | 1,218 ms
159,988 KB |
testcase_10 | AC | 722 ms
160,008 KB |
testcase_11 | AC | 977 ms
160,212 KB |
testcase_12 | AC | 982 ms
160,188 KB |
testcase_13 | AC | 1,025 ms
160,008 KB |
testcase_14 | AC | 1,069 ms
160,020 KB |
testcase_15 | AC | 1,030 ms
160,028 KB |
testcase_16 | AC | 1,035 ms
159,992 KB |
testcase_17 | AC | 1,321 ms
159,992 KB |
testcase_18 | WA | - |
testcase_19 | AC | 1,337 ms
159,212 KB |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
ソースコード
import sys, random input = lambda : sys.stdin.readline().rstrip() write = lambda x: sys.stdout.write(x+"\n"); writef = lambda x: print("{:.12f}".format(x)) debug = lambda x: sys.stderr.write(x+"\n") YES="Yes"; NO="No"; pans = lambda v: print(YES if v else NO); INF=10**18 LI = lambda : list(map(int, input().split())); II=lambda : int(input()); SI=lambda : [ord(c)-ord("a") for c in input()] def debug(_l_): for s in _l_.split(): print(f"{s}={eval(s)}", end=" ") print() def dlist(*l, fill=0): if len(l)==1: return [fill]*l[0] ll = l[1:] return [dlist(*ll, fill=fill) for _ in range(l[0])] n = int(input()) h = list(map(int, input().split())) t = LI() index = list(range(n)) index.sort(key=lambda i: h[i]) pos = [0]*n for i in range(n): pos[index[i]] = i h = [h[ind] for ind in index] t = [t[ind] for ind in index] vs = [0]*n ns = [-1]*n from bisect import bisect_right as br for i in range(n): v = br(h, t[i]) vs[i] = v ns[i] = v-1 cum = ns[:] for i in range(1,n): cum[i] = max(cum[i], cum[i-1]) dns = [cum] for i in range(30): p = dns[-1] l = [-1]*n for j in range(n): if p[j]==-1: l[j] = -1 else: l[j] = max(p[j], p[p[j]]) dns.append(l) q = II() for _ in range(q): a,b = LI() a -= 1 b -= 1 # print(a,b,pos[a],pos[b]) a = pos[a] b = pos[b] res = 1 cur = ns[a] for i in range(30)[::-1]: if dns[i][cur]>=b: continue elif dns[i][cur]!=-1: res += (1<<i) cur = dns[i][cur] else: res = -1 break else: # print(a,cur,b) if dns[0][cur]>=b: res += 1 if ns[a]>=b: res = 1 else: res = -1 print(res)