結果
問題 | No.1332 Range Nearest Query |
ユーザー |
![]() |
提出日時 | 2021-01-09 16:05:21 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,137 bytes |
コンパイル時間 | 322 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 213,208 KB |
最終ジャッジ日時 | 2024-12-11 08:57:00 |
合計ジャッジ時間 | 73,547 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 TLE * 3 |
ソースコード
n = int(input()) *a, = map(int,input().split()) def merge(a,b): la,lb = len(a),len(b) res = [0]*(la+lb) ia = ib = 0 for i in range(la+lb): if ib==lb: res[i:] = a[ia:] return res if ia==la: res[i:] = b[ib:] return res if a[ia] < b[ib]: res[i] = a[ia] ia += 1 else: res[i] = b[ib] ib += 1 return res N0 = 1<<(n-1).bit_length() dat = [[]]*(2*N0) for i in range(n): dat[N0+i] = [a[i]] for k in range(N0-1,0,-1): dat[k] = merge(dat[2*k], dat[2*k+1]) def getans(lst,x): v = INF idx = bisect_left(lst,x) if idx < len(lst): v = lst[idx]-x if idx: v = min(v,x-lst[idx-1]) return v INF = 10**9 from bisect import bisect_left, bisect_right Q = int(input()) for _ in range(Q): L,R,x = map(int,input().split()) L += N0-1; R += N0 ans = INF while L < R: if R & 1: R -= 1 ans = min(ans,getans(dat[R],x)) if L & 1: ans = min(ans,getans(dat[L],x)) L += 1 L >>= 1; R >>= 1 print(ans)