結果
問題 | No.1332 Range Nearest Query |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysinput = lambda: sys.stdin.readline().rstrip()class SegmentTree():def __init__(self, init, unitX, f):self.f = f # (X, X) -> Xself.unitX = unitXself.f = fif type(init) == int:self.n = initself.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.nself.X[i] = xi >>= 1while i:self.X[i] = self.f(self.X[i*2], self.X[i*2|1])i >>= 1def getvalue(self, i):return self.X[i + self.n]def getrange(self, l, r):l += self.nr += self.nal = self.unitXar = self.unitXwhile l < r:if l & 1:al = self.f(al, self.X[l])l += 1if r & 1:r -= 1ar = self.f(self.X[r], ar)l >>= 1r >>= 1return self.f(al, ar)# Find r s.t. calc(l, ..., r-1) = True and calc(l, ..., r) = Falsedef max_right(self, l, z):if l >= self.n: return self.nl += self.ns = self.unitXwhile 1:while l % 2 == 0:l >>= 1if not z(self.f(s, self.X[l])):while l < self.n:l *= 2if z(self.f(s, self.X[l])):s = self.f(s, self.X[l])l += 1return l - self.ns = self.f(s, self.X[l])l += 1if l & -l == l: breakreturn self.n# Find l s.t. calc(l, ..., r-1) = True and calc(l-1, ..., r-1) = Falsedef min_left(self, r, z):if r <= 0: return 0r += self.ns = self.unitXwhile 1:r -= 1while r > 1 and r % 2:r >>= 1if not z(self.f(self.X[r], s)):while r < self.n:r = r * 2 + 1if z(self.f(self.X[r], s)):s = self.f(self.X[r], s)r -= 1return r + 1 - self.ns = self.f(self.X[r], s)if r & -r == r: breakreturn 0def 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] * Qf = maxunit = -10 ** 9st = 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 = minunit = 10 ** 9st = 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)))