結果

問題 No.1332 Range Nearest Query
ユーザー persimmon-persimmon
提出日時 2021-06-15 09:10:21
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,765 bytes
コンパイル時間 993 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 199,336 KB
最終ジャッジ日時 2024-12-26 03:07:29
合計ジャッジ時間 86,693 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 34 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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')
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0