結果

問題 No.1332 Range Nearest Query
コンテスト
ユーザー ああいい
提出日時 2022-03-31 23:06:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,613 ms / 2,500 ms
コード長 4,412 bytes
コンパイル時間 415 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 280,000 KB
最終ジャッジ日時 2024-11-17 16:20:35
合計ジャッジ時間 52,208 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#WaveletMatrix

class BitVector():
    def __init__(self,A):
        self.n = len(A)
        SA = [0] * (self.n + 1)
        for i,a in enumerate(A):
            SA[i+1] = SA[i] + a
        self.SA = SA
    def rank1(self,r):
        return self.SA[r]
    def rank0(self,r):
        return r - self.SA[r]
    def select0(self,k):
        l,r = 0,len(self,SA)
        if not k < r - 1 - self.SA[r-1]:
            return -1
        while r - l > 1:
            m = l + r >> 1
            if m - self.SA[m] <= k:
                l = m
            else:
                r = m
        return l
    def select1(self,k):
        l,r = 0,len(self.SA)
        if not k < self.SA[r-1]:
            return -1
        while r - l > 1:
            m = l + r >> 1
            if self.SA[m] <= k:
                l = m
            else:
                r = m
        return l

class WaveletMatrix():

    # s: word size. Ai <= 10**6 なら 20
    #   Ai <= 10**9 なら　30 ぐらいで
    # (word size < 1 << s となるよう)
    def __init__(self,s,A):
        self.s = s
        self.A = A
        self.n = len(A)
        self.X = []
        B = A.copy()
        for i in reversed(range(s)):
            mask = 1 << i
            L = []
            R = []
            T = []
            for a in B:
                if a & mask:
                    T.append(1)
                    R.append(a)
                else:
                    T.append(0)
                    L.append(a)
            vb = BitVector(T)
            self.X.append((vb.rank0(self.n),vb))
            B = L + R
        self.X = self.X[::-1]
    def access(self,i):
        return self.A[i]
    # A[l,r)内のvalueの数を求める 
    def rank(self,l,r,value):
        if l >= r:return 0
        for i in reversed(range(self.s)):
            z,vb = self.X[i]
            if value >> i & 1:
                l = z + vb.rank1(l)
                r = z + vb.rank1(r)
            else:
                l = vb.rank0(l)
                r = vb.rank0(r)
        return r - l
    def select(self,value,k):
        #A内のk番目のvalueのindexを返す
        #value が k個なければ-1を返す
        if self.rank(0,self.n,value) <= k:return -1
        ind = 0
        for i in reversed(range(self.s)):
            z,v = self.X[i]
            if value >> 1 & 1:
                ind = z + vb.rank1(ind)
            else:
                ind = vb.rank0(int)
        ind += k
        for i in range(self.s):
            z,vb = self.X[i]
            if ind < z:
                ind = vb.select0(ind)
            else:
                ind = vb.select1(ind-z)
        return ind

    def freq_to(self,l,r,value):
        # 0 <= A[i] < value な　数を求める
        if not value:return 0
        if l >= r:return 0
        ret = 0
        for i in reversed(range(self.s)):
            z,vb = self.X[i]
            if value >> i & 1:
                ret += vb.rank0(r) - vb.rank0(l)
                l = z + vb.rank1(l)
                r = z + vb.rank1(r)
            else:
                l = vb.rank0(l)
                r = vb.rank0(r)
        return ret
    
    def freq(self,l,r,d,u):
        # d <= A[i] < u なる数を求める
        if d >= u:return 0
        return self.freq_to(l,r,u) - self.freq_to(l,r,d)

    def quantile(self,l,r,k):
        # [l,r) のk番目に小さい数の返す
        # k: 0-index k = 0で一番小さい数を返す
        if k >= r - l:return -1
        ret = 0
        for i in reversed(range(self.s)):
            z,vb = self.X[i]
            zeros = vb.rank0(r) - vb.rank0(l)
            if zeros > k:
                l = vb.rank0(l)
                r = vb.rank0(r)
            else:
                k -= zeros
                ret |= 1 << i
                l = z + vb.rank1(l)
                r = z + vb.rank1(r)
        return ret
    def quantile2(self,l,r,k):
        #[l,r)のk番目に大きい数を返す
        # k: 0-index
        return self.quantile(l,r,r-l-k-1)

import sys
rr = sys.stdin
N = int(rr.readline())
X = list(map(int,rr.readline().split()))
Q = int(rr.readline())
inf = 10 ** 9 + 5
wm = WaveletMatrix(30,X)
for _ in range(Q):
    l,r,x = map(int,rr.readline().split())
    t = wm.freq_to(l-1,r,x+1)
    ans = inf
    if t > 0:
        u = wm.quantile(l-1,r,t-1)
        ans = x - u
    if t < r - l + 1:
        s = wm.quantile(l-1,r,t)
        ans = min(ans,s - x)
    print(ans)
0