結果
問題 | No.1332 Range Nearest Query |
ユーザー |
![]() |
提出日時 | 2021-01-09 14:25:20 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,800 bytes |
コンパイル時間 | 1,373 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 155,644 KB |
最終ジャッジ日時 | 2024-12-27 11:37:38 |
合計ジャッジ時間 | 71,393 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 TLE * 1 |
ソースコード
import syssys.setrecursionlimit(10**6)int1 = lambda x: int(x)-1p2D = lambda x: print(*x, sep="\n")def II(): return int(sys.stdin.buffer.readline())def MI(): return map(int, sys.stdin.buffer.readline().split())def MI1(): return map(int1, sys.stdin.buffer.readline().split())def LI(): return list(map(int, sys.stdin.buffer.readline().split()))def LI1(): return list(map(int1, sys.stdin.buffer.readline().split()))def LLI(rows_number): return [LI() for _ in range(rows_number)]def BI(): return sys.stdin.buffer.readline().rstrip()def SI(): return sys.stdin.buffer.readline().rstrip().decode()# dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]dij = [[(-1, 0), (1, 0)], [(0, -1), (0, 1)]]inf = 10**16# md = 998244353md = 10**9+7class SegtreeMin():def __init__(self, n):self.inf = 10**16aa = []if not isinstance(n, int):aa = nn = len(aa)self.tree_width = tw = 1 << (n-1).bit_length()self.tree = [self.inf]*(tw*2-1)if aa:self.tree[tw-1:tw-1+len(aa)] = aafor i in range(tw-2, -1, -1):self.tree[i] = min(self.tree[i*2+1], self.tree[i*2+2])def update(self, i, a):seg_i = self.tree_width-1+iself.tree[seg_i] = awhile seg_i != 0:seg_i = (seg_i-1)//2self.tree[seg_i] = min(self.tree[seg_i*2+1], self.tree[seg_i*2+2])def element(self, i):return self.tree[self.tree_width-1+i]# [l,r)の最小値def min(self, l, r):res = self.infstack = [(0, 0, self.tree_width)]while stack:seg_i, segL, segR = stack.pop()if l <= segL and segR <= r:if self.tree[seg_i] < res: res = self.tree[seg_i]else:segM = (segL+segR)//2if r > segL and segM > l:stack.append((seg_i*2+1, segL, segM))if r > segM and segR > l:stack.append((seg_i*2+2, segM, segR))return res# [l,r)でaより小さい要素のうち最右のインデックスdef LessR(self, l, r, a):stack = [(0, 0, self.tree_width)]while stack:u, ul, ur = stack.pop()if ur-ul == 1: return u-self.tree_width+1um = (ul+ur)//2if self.tree[u*2+1] < a and ul < r and l < um:stack.append((u*2+1, ul, um))if self.tree[u*2+2] < a and um < r and l < ur:stack.append((u*2+2, um, ur))return -1# [l,r)でaより小さい要素のうち最左のインデックスdef LessL(self, l, r, a):stack = [(0, 0, self.tree_width)]while stack:u, ul, ur = stack.pop()if ur-ul == 1: return u-self.tree_width+1um = (ul+ur)//2if self.tree[u*2+2] < a and um < r and l < ur:stack.append((u*2+2, um, ur))if self.tree[u*2+1] < a and ul < r and l < um:stack.append((u*2+1, ul, um))return -1class SegtreeMax():def __init__(self, n):self.inf = 10**16aa = []if not isinstance(n, int):aa = nn = len(aa)self.tree_width = tw = 1 << (n-1).bit_length()self.tree = [-self.inf]*(tw*2-1)if aa:self.tree[tw-1:tw-1+len(aa)] = aafor i in range(tw-2, -1, -1):self.tree[i] = max(self.tree[i*2+1], self.tree[i*2+2])def update(self, i, a):seg_i = self.tree_width-1+iself.tree[seg_i] = awhile seg_i != 0:seg_i = (seg_i-1)//2self.tree[seg_i] = max(self.tree[seg_i*2+1], self.tree[seg_i*2+2])def element(self, i):return self.tree[self.tree_width-1+i]# [l,r)の最小値def max(self, l, r):res = -self.infstack = [(0, 0, self.tree_width)]while stack:seg_i, segL, segR = stack.pop()if l <= segL and segR <= r:if self.tree[seg_i] > res: res = self.tree[seg_i]else:segM = (segL+segR)//2if r > segL and segM > l:stack.append((seg_i*2+1, segL, segM))if r > segM and segR > l:stack.append((seg_i*2+2, segM, segR))return res# [l,r)でaより大きい要素のうち最右のインデックスdef OverR(self, l, r, a):stack = [(0, 0, self.tree_width)]while stack:u, ul, ur = stack.pop()if ur-ul == 1: return u-self.tree_width+1um = (ul+ur)//2if self.tree[u*2+1] > a and ul < r and l < um:stack.append((u*2+1, ul, um))if self.tree[u*2+2] > a and um < r and l < ur:stack.append((u*2+2, um, ur))return -1# [l,r)でaより大きい要素のうち最左のインデックスdef OverL(self, l, r, a):stack = [(0, 0, self.tree_width)]while stack:u, ul, ur = stack.pop()if ur-ul == 1: return u-self.tree_width+1um = (ul+ur)//2if self.tree[u*2+2] > a and um < r and l < ur:stack.append((u*2+2, um, ur))if self.tree[u*2+1] > a and ul < r and l < um:stack.append((u*2+1, ul, um))return -1n=II()xx=LI()q=II()xlri=[]for i in range(q):l,r,x=MI()l-=1xlri.append((x,l,r,i))xlri.sort()mn=SegtreeMin(xx)mx=SegtreeMax(n)ans=[-1]*qxj=[(x,j) for j,x in enumerate(xx)]xj.sort(reverse=True)for x,l,r,i in xlri:while xj and xj[-1][0]<x:x0,j=xj.pop()mn.update(j,inf)mx.update(j,x0)ans[i]=min(mn.min(l,r)-x,x-mx.max(l,r))print(*ans,sep="\n")