結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
52,992 KB
testcase_01 AC 34 ms
52,992 KB
testcase_02 AC 34 ms
53,248 KB
testcase_03 AC 1,508 ms
274,584 KB
testcase_04 AC 1,490 ms
275,664 KB
testcase_05 AC 1,474 ms
277,776 KB
testcase_06 AC 1,235 ms
276,136 KB
testcase_07 AC 1,249 ms
276,256 KB
testcase_08 AC 1,275 ms
277,000 KB
testcase_09 AC 1,284 ms
276,404 KB
testcase_10 AC 1,237 ms
276,524 KB
testcase_11 AC 1,211 ms
276,416 KB
testcase_12 AC 1,168 ms
276,280 KB
testcase_13 AC 1,207 ms
276,656 KB
testcase_14 AC 1,187 ms
276,400 KB
testcase_15 AC 1,356 ms
276,144 KB
testcase_16 AC 1,594 ms
277,936 KB
testcase_17 AC 1,613 ms
279,668 KB
testcase_18 AC 1,572 ms
278,700 KB
testcase_19 AC 1,543 ms
278,808 KB
testcase_20 AC 1,590 ms
278,984 KB
testcase_21 AC 1,549 ms
279,240 KB
testcase_22 AC 1,585 ms
279,512 KB
testcase_23 AC 1,587 ms
279,768 KB
testcase_24 AC 1,580 ms
280,000 KB
testcase_25 AC 1,563 ms
277,424 KB
testcase_26 AC 720 ms
274,296 KB
testcase_27 AC 728 ms
274,684 KB
testcase_28 AC 228 ms
78,976 KB
testcase_29 AC 229 ms
79,852 KB
testcase_30 AC 231 ms
80,132 KB
testcase_31 AC 240 ms
79,616 KB
testcase_32 AC 287 ms
80,896 KB
testcase_33 AC 281 ms
80,928 KB
testcase_34 AC 212 ms
78,976 KB
testcase_35 AC 215 ms
79,376 KB
testcase_36 AC 213 ms
78,968 KB
testcase_37 AC 232 ms
79,868 KB
testcase_38 AC 1,191 ms
259,652 KB
testcase_39 AC 522 ms
83,148 KB
testcase_40 AC 1,536 ms
276,968 KB
testcase_41 AC 761 ms
133,884 KB
testcase_42 AC 1,154 ms
259,664 KB
testcase_43 AC 952 ms
192,876 KB
testcase_44 AC 1,358 ms
261,412 KB
testcase_45 AC 1,329 ms
259,984 KB
testcase_46 AC 1,110 ms
258,708 KB
testcase_47 AC 1,235 ms
260,896 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