結果
問題 | No.1332 Range Nearest Query |
ユーザー | persimmon-persimmon |
提出日時 | 2021-02-14 10:36:08 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,157 bytes |
コンパイル時間 | 969 ms |
コンパイル使用メモリ | 85,700 KB |
実行使用メモリ | 300,392 KB |
最終ジャッジ日時 | 2023-09-28 21:31:57 |
合計ジャッジ時間 | 90,948 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 86 ms
71,320 KB |
testcase_01 | AC | 89 ms
71,104 KB |
testcase_02 | AC | 86 ms
71,212 KB |
testcase_03 | TLE | - |
testcase_04 | TLE | - |
testcase_05 | TLE | - |
testcase_06 | AC | 1,741 ms
298,972 KB |
testcase_07 | AC | 1,708 ms
299,124 KB |
testcase_08 | AC | 1,725 ms
299,072 KB |
testcase_09 | AC | 1,760 ms
299,060 KB |
testcase_10 | AC | 1,765 ms
299,236 KB |
testcase_11 | AC | 1,732 ms
299,244 KB |
testcase_12 | AC | 1,710 ms
299,228 KB |
testcase_13 | AC | 1,753 ms
299,200 KB |
testcase_14 | AC | 1,744 ms
299,240 KB |
testcase_15 | AC | 1,781 ms
299,164 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 | 999 ms
278,312 KB |
testcase_27 | AC | 1,015 ms
299,556 KB |
testcase_28 | AC | 652 ms
106,364 KB |
testcase_29 | AC | 729 ms
107,136 KB |
testcase_30 | AC | 824 ms
108,416 KB |
testcase_31 | AC | 450 ms
104,780 KB |
testcase_32 | AC | 838 ms
107,800 KB |
testcase_33 | AC | 844 ms
108,480 KB |
testcase_34 | AC | 576 ms
105,764 KB |
testcase_35 | AC | 671 ms
106,628 KB |
testcase_36 | AC | 668 ms
106,972 KB |
testcase_37 | AC | 719 ms
107,224 KB |
testcase_38 | AC | 2,103 ms
202,836 KB |
testcase_39 | AC | 1,166 ms
146,496 KB |
testcase_40 | TLE | - |
testcase_41 | AC | 1,403 ms
162,956 KB |
testcase_42 | AC | 1,994 ms
200,584 KB |
testcase_43 | AC | 1,642 ms
169,980 KB |
testcase_44 | AC | 2,253 ms
271,616 KB |
testcase_45 | AC | 2,086 ms
268,620 KB |
testcase_46 | AC | 1,988 ms
190,224 KB |
testcase_47 | AC | 1,957 ms
232,212 KB |
ソースコード
def main0(n,xary,q,lrx): ret=[] inf=float('inf') for l,r,x in lrx: tmp=inf for y in range(l-1,r): tmp=min(tmp,abs(xary[y]-x)) ret.append(tmp) return ret 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)] 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:break if x not in didx:continue for i in didx[x]: mxst.update(i,x) mnst.update(i,inf) print(*ret,sep='\n')