結果

問題 No.1332 Range Nearest Query
ユーザー Kiri8128Kiri8128
提出日時 2021-01-08 23:15:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,382 bytes
コンパイル時間 368 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 182,192 KB
最終ジャッジ日時 2024-11-16 17:28:44
合計ジャッジ時間 48,200 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 25 WA * 23
権限があれば一括ダウンロードができます

ソースコード

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

import sys
input = lambda: sys.stdin.readline().rstrip()
class SegmentTree():
def __init__(self, init, unitX, f):
self.f = f # (X, X) -> X
self.unitX = unitX
self.f = f
if type(init) == int:
self.n = init
self.n = 1 << (self.n - 1).bit_length()
self.X = [unitX] * (self.n * 2)
else:
self.n = len(init)
self.n = 1 << (self.n - 1).bit_length()
self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
for i in range(self.n-1, 0, -1):
self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
def update(self, i, x):
i += self.n
self.X[i] = x
i >>= 1
while i:
self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
i >>= 1
def getvalue(self, i):
return self.X[i + self.n]
def getrange(self, l, r):
l += self.n
r += self.n
al = self.unitX
ar = self.unitX
while l < r:
if l & 1:
al = self.f(al, self.X[l])
l += 1
if r & 1:
r -= 1
ar = self.f(self.X[r], ar)
l >>= 1
r >>= 1
return self.f(al, ar)
# Find r s.t. calc(l, ..., r-1) = True and calc(l, ..., r) = False
def max_right(self, l, z):
if l >= self.n: return self.n
l += self.n
s = self.unitX
while 1:
while l % 2 == 0:
l >>= 1
if not z(self.f(s, self.X[l])):
while l < self.n:
l *= 2
if z(self.f(s, self.X[l])):
s = self.f(s, self.X[l])
l += 1
return l - self.n
s = self.f(s, self.X[l])
l += 1
if l & -l == l: break
return self.n
# Find l s.t. calc(l, ..., r-1) = True and calc(l-1, ..., r-1) = False
def min_left(self, r, z):
if r <= 0: return 0
r += self.n
s = self.unitX
while 1:
r -= 1
while r > 1 and r % 2:
r >>= 1
if not z(self.f(self.X[r], s)):
while r < self.n:
r = r * 2 + 1
if z(self.f(self.X[r], s)):
s = self.f(self.X[r], s)
r -= 1
return r + 1 - self.n
s = self.f(self.X[r], s)
if r & -r == r: break
return 0
def debug(self):
print("debug")
print([self.getvalue(i) for i in range(min(self.n, 20))])
N = int(input())
X = [int(a) for a in input().split()]
Y = []
Q = int(input())
for i in range(Q):
l, r, x = map(int, input().split())
Y.append((l-1, r, x, i))
for i, x in enumerate(X):
Y.append((-1, -1, x, i))
Y.sort(key = lambda x: x[2])
ANS = [10 ** 9] * Q
f = max
unit = -10 ** 9
st = SegmentTree(N + 2, unit, f)
for l, r, x, i in Y:
if l >= 0:
m = st.getrange(l, r)
ANS[i] = min(ANS[i], x - m)
else:
st.update(i, x)
f = min
unit = 10 ** 9
st = SegmentTree(N + 2, unit, f)
for l, r, x, i in Y[::-1]:
if l >= 0:
m = st.getrange(l, r)
ANS[i] = min(ANS[i], m - x)
else:
st.update(i, x)
print("\n".join(map(str, ANS)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0