結果
問題 | No.1332 Range Nearest Query |
ユーザー | aaaaaaaaaa2230 |
提出日時 | 2021-01-08 23:00:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,327 ms / 2,500 ms |
コード長 | 1,895 bytes |
コンパイル時間 | 410 ms |
コンパイル使用メモリ | 86,964 KB |
実行使用メモリ | 259,180 KB |
最終ジャッジ日時 | 2023-08-10 11:26:06 |
合計ジャッジ時間 | 64,072 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,400 KB |
testcase_01 | AC | 71 ms
71,080 KB |
testcase_02 | AC | 76 ms
71,216 KB |
testcase_03 | AC | 2,210 ms
244,364 KB |
testcase_04 | AC | 2,327 ms
242,444 KB |
testcase_05 | AC | 2,241 ms
244,052 KB |
testcase_06 | AC | 722 ms
251,500 KB |
testcase_07 | AC | 769 ms
250,848 KB |
testcase_08 | AC | 705 ms
250,968 KB |
testcase_09 | AC | 718 ms
250,852 KB |
testcase_10 | AC | 728 ms
250,716 KB |
testcase_11 | AC | 721 ms
250,948 KB |
testcase_12 | AC | 719 ms
251,128 KB |
testcase_13 | AC | 723 ms
250,936 KB |
testcase_14 | AC | 731 ms
251,028 KB |
testcase_15 | AC | 715 ms
251,492 KB |
testcase_16 | AC | 2,265 ms
252,412 KB |
testcase_17 | AC | 2,226 ms
252,136 KB |
testcase_18 | AC | 2,262 ms
252,160 KB |
testcase_19 | AC | 2,210 ms
252,768 KB |
testcase_20 | AC | 2,238 ms
252,388 KB |
testcase_21 | AC | 2,212 ms
253,352 KB |
testcase_22 | AC | 2,214 ms
252,768 KB |
testcase_23 | AC | 2,261 ms
252,400 KB |
testcase_24 | AC | 2,266 ms
252,696 KB |
testcase_25 | AC | 2,241 ms
252,628 KB |
testcase_26 | AC | 550 ms
250,116 KB |
testcase_27 | AC | 560 ms
259,180 KB |
testcase_28 | AC | 255 ms
96,544 KB |
testcase_29 | AC | 280 ms
97,448 KB |
testcase_30 | AC | 351 ms
96,852 KB |
testcase_31 | AC | 193 ms
94,276 KB |
testcase_32 | AC | 357 ms
97,680 KB |
testcase_33 | AC | 386 ms
98,328 KB |
testcase_34 | AC | 229 ms
95,592 KB |
testcase_35 | AC | 263 ms
96,424 KB |
testcase_36 | AC | 255 ms
95,480 KB |
testcase_37 | AC | 294 ms
97,336 KB |
testcase_38 | AC | 1,887 ms
170,416 KB |
testcase_39 | AC | 1,109 ms
108,348 KB |
testcase_40 | AC | 2,181 ms
250,676 KB |
testcase_41 | AC | 1,453 ms
124,880 KB |
testcase_42 | AC | 1,804 ms
167,872 KB |
testcase_43 | AC | 1,618 ms
139,796 KB |
testcase_44 | AC | 2,025 ms
203,692 KB |
testcase_45 | AC | 1,855 ms
193,980 KB |
testcase_46 | AC | 1,794 ms
148,640 KB |
testcase_47 | AC | 1,871 ms
185,344 KB |
ソースコード
import sys input = sys.stdin.readline from bisect import bisect_left class SegTree: """ define what you want to do with 0 index, ex) size = tree_size, func = min or max, sta = default_value """ def __init__(self,size): self.n = size self.size = 1 << size.bit_length() self.tree = [[] for i in range(2*self.size)] def build(self, list): """ set list and update tree""" for i,x in enumerate(list,self.size): self.tree[i] = [x] for i in range(self.size-1,0,-1): self.tree[i] = sorted(self.tree[i<<1]+self.tree[i<<1 | 1]) def get(self,l,r,x): """ take the value of [l r) with func (min or max)""" l += self.size r += self.size res = 10**10 while l < r: if l & 1: if x <= self.tree[l][0]: res = min(res,self.tree[l][0]-x) elif x >= self.tree[l][-1]: res = min(res,x-self.tree[l][-1]) else: t = bisect_left(self.tree[l],x) res = min(res,x-self.tree[l][t-1],self.tree[l][t]-x) l += 1 if r & 1: if x <= self.tree[r-1][0]: res = min(res,self.tree[r-1][0]-x) elif x >= self.tree[r-1][-1]: res = min(res,x-self.tree[r-1][-1]) else: t = bisect_left(self.tree[r-1],x) res = min(res,x-self.tree[r-1][t-1],self.tree[r-1][t]-x) l >>= 1 r >>= 1 if res == 0: return res return res n = int(input()) X = list(map(int,input().split())) Q = int(input()) q = [tuple(map(int,input().split())) for i in range(Q)] seg = SegTree(n) seg.build(X) ans = [] for l,r,x in q: ans.append(seg.get(l-1,r,x)) print(*ans,sep="\n")