結果

問題 No.1332 Range Nearest Query
ユーザー ああいいああいい
提出日時 2022-03-31 23:06:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,984 ms / 2,500 ms
コード長 4,412 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 280,156 KB
最終ジャッジ日時 2024-04-28 20:41:32
合計ジャッジ時間 67,323 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,248 KB
testcase_01 AC 40 ms
53,120 KB
testcase_02 AC 40 ms
53,632 KB
testcase_03 AC 1,846 ms
274,456 KB
testcase_04 AC 1,860 ms
275,392 KB
testcase_05 AC 1,922 ms
277,396 KB
testcase_06 AC 1,600 ms
276,768 KB
testcase_07 AC 1,486 ms
276,772 KB
testcase_08 AC 1,489 ms
277,100 KB
testcase_09 AC 1,541 ms
276,668 KB
testcase_10 AC 1,512 ms
276,316 KB
testcase_11 AC 1,564 ms
276,668 KB
testcase_12 AC 1,476 ms
276,408 KB
testcase_13 AC 1,499 ms
276,532 KB
testcase_14 AC 1,516 ms
276,788 KB
testcase_15 AC 1,482 ms
276,776 KB
testcase_16 AC 1,976 ms
278,820 KB
testcase_17 AC 1,972 ms
279,820 KB
testcase_18 AC 1,914 ms
278,572 KB
testcase_19 AC 1,935 ms
279,452 KB
testcase_20 AC 1,955 ms
278,916 KB
testcase_21 AC 1,937 ms
280,020 KB
testcase_22 AC 1,979 ms
279,500 KB
testcase_23 AC 1,984 ms
280,156 KB
testcase_24 AC 1,976 ms
280,000 KB
testcase_25 AC 1,911 ms
277,812 KB
testcase_26 AC 839 ms
274,944 KB
testcase_27 AC 857 ms
274,684 KB
testcase_28 AC 289 ms
79,324 KB
testcase_29 AC 294 ms
80,016 KB
testcase_30 AC 299 ms
80,008 KB
testcase_31 AC 304 ms
79,956 KB
testcase_32 AC 362 ms
81,152 KB
testcase_33 AC 358 ms
81,132 KB
testcase_34 AC 274 ms
79,232 KB
testcase_35 AC 281 ms
80,160 KB
testcase_36 AC 272 ms
79,224 KB
testcase_37 AC 300 ms
80,376 KB
testcase_38 AC 1,658 ms
260,132 KB
testcase_39 AC 702 ms
83,744 KB
testcase_40 AC 1,848 ms
277,100 KB
testcase_41 AC 1,250 ms
134,016 KB
testcase_42 AC 1,628 ms
260,116 KB
testcase_43 AC 1,471 ms
193,384 KB
testcase_44 AC 1,781 ms
261,544 KB
testcase_45 AC 1,744 ms
260,412 KB
testcase_46 AC 1,540 ms
258,972 KB
testcase_47 AC 1,640 ms
260,768 KB
権限があれば一括ダウンロードができます

ソースコード

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