結果
問題 | No.1332 Range Nearest Query |
ユーザー | persimmon-persimmon |
提出日時 | 2021-06-15 09:10:21 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,765 bytes |
コンパイル時間 | 787 ms |
コンパイル使用メモリ | 86,672 KB |
実行使用メモリ | 196,216 KB |
最終ジャッジ日時 | 2023-08-26 23:25:16 |
合計ジャッジ時間 | 76,118 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
71,288 KB |
testcase_01 | AC | 75 ms
71,252 KB |
testcase_02 | AC | 77 ms
71,504 KB |
testcase_03 | AC | 2,267 ms
176,848 KB |
testcase_04 | AC | 2,342 ms
176,764 KB |
testcase_05 | AC | 2,324 ms
177,372 KB |
testcase_06 | AC | 1,232 ms
190,428 KB |
testcase_07 | AC | 1,224 ms
190,464 KB |
testcase_08 | AC | 1,209 ms
190,844 KB |
testcase_09 | AC | 1,196 ms
191,272 KB |
testcase_10 | AC | 1,204 ms
190,588 KB |
testcase_11 | AC | 1,205 ms
190,668 KB |
testcase_12 | AC | 1,213 ms
190,644 KB |
testcase_13 | AC | 1,193 ms
190,736 KB |
testcase_14 | AC | 1,193 ms
191,176 KB |
testcase_15 | AC | 1,259 ms
190,828 KB |
testcase_16 | AC | 2,472 ms
195,392 KB |
testcase_17 | TLE | - |
testcase_18 | AC | 2,497 ms
194,128 KB |
testcase_19 | TLE | - |
testcase_20 | AC | 2,495 ms
194,240 KB |
testcase_21 | AC | 2,465 ms
194,796 KB |
testcase_22 | TLE | - |
testcase_23 | AC | 2,486 ms
195,064 KB |
testcase_24 | AC | 2,407 ms
194,212 KB |
testcase_25 | TLE | - |
testcase_26 | AC | 798 ms
187,024 KB |
testcase_27 | AC | 870 ms
192,008 KB |
testcase_28 | AC | 501 ms
104,988 KB |
testcase_29 | AC | 546 ms
104,768 KB |
testcase_30 | AC | 621 ms
105,624 KB |
testcase_31 | AC | 386 ms
104,140 KB |
testcase_32 | AC | 604 ms
105,816 KB |
testcase_33 | AC | 640 ms
106,116 KB |
testcase_34 | AC | 463 ms
104,544 KB |
testcase_35 | AC | 523 ms
105,064 KB |
testcase_36 | AC | 506 ms
104,788 KB |
testcase_37 | AC | 564 ms
105,032 KB |
testcase_38 | AC | 1,733 ms
139,180 KB |
testcase_39 | AC | 1,022 ms
114,440 KB |
testcase_40 | TLE | - |
testcase_41 | AC | 1,238 ms
116,264 KB |
testcase_42 | AC | 1,730 ms
141,776 KB |
testcase_43 | AC | 1,367 ms
123,688 KB |
testcase_44 | AC | 1,965 ms
157,492 KB |
testcase_45 | AC | 1,916 ms
152,892 KB |
testcase_46 | AC | 1,636 ms
133,932 KB |
testcase_47 | AC | 1,772 ms
151,504 KB |
ソースコード
import sys input=sys.stdin.readline class SegmentTree(): def __init__(self,size,f=lambda x,y:x+y,default=0): self.size=pow(2,(size-1).bit_length()) self.f=f self.default=default self.data=[default]*(self.size*2) # list[i]をxに更新 def update(self,i,x): i+=self.size self.data[i]=x while i: i>>=1 self.data[i]=self.f(self.data[i*2],self.data[i*2+1]) # はじめの構築をO(N)で行う def init_build(self,ary): n=len(ary) for i in range(n): self.data[i+self.size]=ary[i] for i in reversed(range(self.size)): self.data[i]=self.f(self.data[i*2],self.data[i*2+1]) # 区間[l,r)へのクエリ def query(self,l,r): l,r=l+self.size,r+self.size lret,rret=self.default,self.default while l<r: if l&1: lret=self.f(self.data[l],lret) l+=1 if r&1: r-=1 rret=self.f(self.data[r],rret) l>>=1 r>>=1 return self.f(lret,rret) def get(self,i): return self.data[self.size+i] n=int(input()) xary=list(map(int,input().split())) q=int(input()) lrx=[list(map(int,input().split())) for _ in range(q)] events=[] for i,x in enumerate(xary): events.append([x,i]) for i,(l,r,x) in enumerate(lrx): events.append([x,i+n]) events.sort(key=lambda x:x[0]) inf=float('inf') def max(x,y): if x>y:return x return y def min(x,y): if x<y:return x return y mxst=SegmentTree(n,max,-inf) mnst=SegmentTree(n,min,inf) mnst.init_build(xary) ret=[None]*q idx=0 for x,i in events: if i<n: mxst.update(i,x) mnst.update(i,inf) else: l,r,x=lrx[i-n] y=mnst.query(l-1,r) z=mxst.query(l-1,r) tmp=inf if y!=inf:tmp=min(tmp,abs(x-y)) if z!=-inf:tmp=min(tmp,abs(x-z)) ret[i-n]=tmp print(*ret,sep='\n')