結果
問題 | No.2242 Cities and Teleporters |
ユーザー | shotoyoo |
提出日時 | 2023-03-10 22:48:07 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,918 bytes |
コンパイル時間 | 1,746 ms |
コンパイル使用メモリ | 81,508 KB |
実行使用メモリ | 162,976 KB |
最終ジャッジ日時 | 2023-10-18 08:28:27 |
合計ジャッジ時間 | 29,135 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
56,008 KB |
testcase_01 | AC | 42 ms
56,008 KB |
testcase_02 | AC | 42 ms
56,008 KB |
testcase_03 | AC | 42 ms
56,008 KB |
testcase_04 | WA | - |
testcase_05 | AC | 1,335 ms
162,976 KB |
testcase_06 | AC | 863 ms
153,936 KB |
testcase_07 | AC | 1,278 ms
159,936 KB |
testcase_08 | AC | 1,206 ms
159,880 KB |
testcase_09 | AC | 1,219 ms
159,924 KB |
testcase_10 | AC | 721 ms
159,940 KB |
testcase_11 | AC | 984 ms
160,128 KB |
testcase_12 | AC | 990 ms
160,140 KB |
testcase_13 | AC | 997 ms
159,940 KB |
testcase_14 | AC | 1,063 ms
159,952 KB |
testcase_15 | AC | 1,017 ms
159,964 KB |
testcase_16 | AC | 1,019 ms
159,924 KB |
testcase_17 | AC | 1,296 ms
159,924 KB |
testcase_18 | AC | 1,078 ms
159,204 KB |
testcase_19 | AC | 1,334 ms
159,152 KB |
testcase_20 | AC | 979 ms
158,248 KB |
testcase_21 | AC | 989 ms
157,288 KB |
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] if cur==-1: res = -1 else: 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)