結果
問題 | No.1332 Range Nearest Query |
ユーザー | persimmon-persimmon |
提出日時 | 2021-02-14 10:32:30 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,158 bytes |
コンパイル時間 | 651 ms |
コンパイル使用メモリ | 86,760 KB |
実行使用メモリ | 282,928 KB |
最終ジャッジ日時 | 2023-09-28 21:26:55 |
合計ジャッジ時間 | 63,909 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 87 ms
71,548 KB |
testcase_01 | AC | 89 ms
71,296 KB |
testcase_02 | AC | 92 ms
71,564 KB |
testcase_03 | TLE | - |
testcase_04 | TLE | - |
testcase_05 | AC | 2,349 ms
267,256 KB |
testcase_06 | AC | 1,317 ms
280,752 KB |
testcase_07 | AC | 1,325 ms
281,012 KB |
testcase_08 | AC | 1,352 ms
280,836 KB |
testcase_09 | AC | 1,359 ms
280,980 KB |
testcase_10 | AC | 1,353 ms
280,836 KB |
testcase_11 | AC | 1,309 ms
281,044 KB |
testcase_12 | AC | 1,328 ms
280,844 KB |
testcase_13 | AC | 1,361 ms
280,828 KB |
testcase_14 | AC | 1,355 ms
281,016 KB |
testcase_15 | AC | 1,359 ms
280,920 KB |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | AC | 1,008 ms
274,920 KB |
testcase_27 | AC | 703 ms
282,928 KB |
testcase_28 | AC | 627 ms
106,216 KB |
testcase_29 | AC | 782 ms
106,316 KB |
testcase_30 | AC | 783 ms
107,360 KB |
testcase_31 | AC | 452 ms
105,100 KB |
testcase_32 | AC | 772 ms
107,468 KB |
testcase_33 | AC | 785 ms
106,856 KB |
testcase_34 | AC | 586 ms
105,624 KB |
testcase_35 | AC | 641 ms
105,968 KB |
testcase_36 | AC | 630 ms
106,804 KB |
testcase_37 | AC | 665 ms
105,884 KB |
testcase_38 | AC | 1,845 ms
193,628 KB |
testcase_39 | AC | 1,161 ms
146,572 KB |
testcase_40 | TLE | - |
testcase_41 | AC | 1,417 ms
162,948 KB |
testcase_42 | AC | 1,849 ms
194,672 KB |
testcase_43 | AC | 1,591 ms
163,820 KB |
testcase_44 | AC | 2,217 ms
271,744 KB |
testcase_45 | AC | 2,019 ms
269,008 KB |
testcase_46 | AC | 1,759 ms
184,692 KB |
testcase_47 | AC | 1,906 ms
232,304 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] def main1(n,xary,q,lrx): s=set(xary) for l,r,x in lrx:s.add(x) s=list(s) s.sort() numx=len(s) d={si:i for i,si in enumerate(s)} dr={i:si for i,si in enumerate(s)} didx={} for i,xv in enumerate(xary): xv=d[xv] if xv in didx: didx[xv].add(i) else: didx[xv]={i} del s inf=float('inf') mxst=SegmentTree(n,max,-inf) mnst=SegmentTree(n,min,inf) mnst.init_build([d[x] for x in xary]) lrx=[[d[x],l,r,i] for i,(l,r,x) in enumerate(lrx)] lrx.sort() ret=[None]*q idx=0 for x in range(numx): while idx<q and lrx[idx][0]==x: _,l,r,i=lrx[idx] y=mnst.query(l-1,r) z=mxst.query(l-1,r) tmp=inf if y!=inf:tmp=min(tmp,abs(dr[x]-dr[y])) if z!=-inf:tmp=min(tmp,abs(dr[x]-dr[z])) ret[i]=tmp idx+=1 if idx==q:return ret if x not in didx:continue for i in didx[x]: mxst.update(i,x) mnst.update(i,inf) return ret if __name__=='__main__': n=int(input()) xary=list(map(int,input().split())) q=int(input()) lrx=[list(map(int,input().split())) for _ in range(q)] ret1=main1(n,xary,q,lrx) print(*ret1,sep='\n')