結果
問題 | No.1332 Range Nearest Query |
ユーザー |
|
提出日時 | 2021-06-15 09:08:19 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,679 bytes |
コンパイル時間 | 1,441 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 191,788 KB |
最終ジャッジ日時 | 2024-12-26 03:04:34 |
合計ジャッジ時間 | 78,391 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 WA * 33 TLE * 11 |
ソースコード
import sysinput=sys.stdin.readlineclass SegmentTree():def __init__(self,size,f=lambda x,y:x+y,default=0):self.size=pow(2,(size-1).bit_length())self.f=fself.default=defaultself.data=[default]*(self.size*2)# list[i]をxに更新def update(self,i,x):i+=self.sizeself.data[i]=xwhile i:i>>=1self.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.sizelret,rret=self.default,self.defaultwhile l<r:if l&1:lret=self.f(self.data[l],lret)l+=1if r&1:r-=1rret=self.f(self.data[r],rret)l>>=1r>>=1return 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')mxst=SegmentTree(n,max,0)mnst=SegmentTree(n,min,inf)mnst.init_build(xary)ret=[None]*qidx=0for 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=infif y!=inf:tmp=min(tmp,abs(x-y))if z!=-inf:tmp=min(tmp,abs(x-z))ret[i-n]=tmpprint(*ret,sep='\n')