結果

問題 No.1332 Range Nearest Query
コンテスト
ユーザー yt142857
提出日時 2026-05-13 12:34:27
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 2,341 ms / 2,500 ms
コード長 1,873 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 395 ms
コンパイル使用メモリ 85,152 KB
実行使用メモリ 305,884 KB
最終ジャッジ日時 2026-05-13 12:35:51
合計ジャッジ時間 81,423 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class wavlet_matrix:
  def __init__(self,lis):
    self.log = 0
    self.N = len(lis);
    self.maxi = max(lis)
    while ((1 << self.log) - 1 < self.maxi):
      self.log += 1
    self.matrix = []
    mae = lis[:]
    for i in range(self.log-1,-1,-1):
      nxt = [0]
      _zero = []
      _one = []
      for j in range(len(mae)):
        nxt.append(nxt[-1] + ((mae[j] >> i) & 1))
        if ((mae[j] >> i) & 1) == 0:
          _zero.append(mae[j])
        else:
          _one.append(mae[j])
      self.matrix.append(nxt)
      mae = _zero + _one
    self.matrix.reverse()
  def get_subtree_range(self,h,l,r):
    a0 = l - self.matrix[h][l]
    a1 = self.matrix[h][l]
    b0 = r - self.matrix[h][r]
    b1 = self.matrix[h][r]
    c0 = self.N - self.matrix[h][self.N];
    return (a0, b0, c0 + a1, c0 + b1)
  def _get_kth_smaller(self,h,l,r,k):
    if h == 0:
      return 0
    l0,r0,l1,r1 = self.get_subtree_range(h-1,l,r)
    if (k < r0-l0):
      return self._get_kth_smaller(h-1,l0,r0,k)
    else:
      return (1 << (h - 1)) + self._get_kth_smaller(h-1,l1,r1,k - (r0-l0))
  def kth(self,l,r,k):
    return self._get_kth_smaller(self.log,l,r,k)
  
  def less_than(self,l,r,k):
    if k <= 0:
      return 0
    if k >= (1 << self.log):
      return r - l
    h = self.log
    re = 0
    now = 0
    for i in range(h-1,-1,-1):
      l0,r0,l1,r1 = self.get_subtree_range(i,l,r)
      if (now + (1 << i) < k):
        now += (1<<i)
        re += r0-l0
        l,r = l1,r1
      else:
        l,r = l0,r0
    re += r-l
    return re
n = int(input())
s = [int(_) for _ in input().split()]
wa = wavlet_matrix(s)
q = int(input())
for _ in range(q):
  a,b,c = [int(_) for _ in input().split()]
  ans = 10**10
  idx = wa.less_than(a-1,b,c)
  if idx > 0:
    ans = min(ans,abs(wa.kth(a-1,b,idx-1)-c))
  if idx < b-a+1:
    ans = min(ans,abs(wa.kth(a-1,b,idx)-c))
  print(ans)
0