結果
問題 | No.2242 Cities and Teleporters |
ユーザー | shotoyoo |
提出日時 | 2023-03-10 23:05:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,263 ms / 3,000 ms |
コード長 | 1,930 bytes |
コンパイル時間 | 798 ms |
コンパイル使用メモリ | 81,516 KB |
実行使用メモリ | 162,932 KB |
最終ジャッジ日時 | 2023-10-18 08:48:30 |
合計ジャッジ時間 | 24,090 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
55,984 KB |
testcase_01 | AC | 41 ms
55,984 KB |
testcase_02 | AC | 43 ms
55,984 KB |
testcase_03 | AC | 42 ms
55,984 KB |
testcase_04 | AC | 44 ms
55,984 KB |
testcase_05 | AC | 983 ms
162,932 KB |
testcase_06 | AC | 776 ms
153,900 KB |
testcase_07 | AC | 1,032 ms
159,852 KB |
testcase_08 | AC | 1,159 ms
159,820 KB |
testcase_09 | AC | 1,133 ms
159,820 KB |
testcase_10 | AC | 694 ms
159,844 KB |
testcase_11 | AC | 863 ms
160,020 KB |
testcase_12 | AC | 861 ms
160,120 KB |
testcase_13 | AC | 903 ms
160,000 KB |
testcase_14 | AC | 1,010 ms
159,864 KB |
testcase_15 | AC | 879 ms
159,860 KB |
testcase_16 | AC | 990 ms
159,856 KB |
testcase_17 | AC | 1,263 ms
159,824 KB |
testcase_18 | AC | 744 ms
159,140 KB |
testcase_19 | AC | 751 ms
159,032 KB |
testcase_20 | AC | 1,060 ms
158,112 KB |
testcase_21 | AC | 929 ms
157,224 KB |
testcase_22 | AC | 710 ms
157,528 KB |
testcase_23 | AC | 729 ms
159,784 KB |
testcase_24 | AC | 713 ms
159,776 KB |
testcase_25 | AC | 698 ms
159,788 KB |
ソースコード
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[:] cum[0] = max(cum[0], 0) for i in range(1,n): cum[i] = max(i, 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 or dns[-1][cur]==-1 or dns[-1][cur]<b: res = -1 elif cur>=b: 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: if dns[0][cur]>=b: res += 1 else: res = -1 print(res)