結果

問題 No.2161 Black Market
ユーザー 👑 KazunKazun
提出日時 2022-12-12 18:37:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,433 ms / 7,000 ms
コード長 8,510 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 260,628 KB
最終ジャッジ日時 2024-04-24 09:47:34
合計ジャッジ時間 11,120 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
55,552 KB
testcase_01 AC 42 ms
55,680 KB
testcase_02 AC 91 ms
76,800 KB
testcase_03 AC 43 ms
55,424 KB
testcase_04 AC 43 ms
55,552 KB
testcase_05 AC 42 ms
55,296 KB
testcase_06 AC 87 ms
76,800 KB
testcase_07 AC 86 ms
77,056 KB
testcase_08 AC 118 ms
77,740 KB
testcase_09 AC 106 ms
76,916 KB
testcase_10 AC 113 ms
78,592 KB
testcase_11 AC 99 ms
77,440 KB
testcase_12 AC 81 ms
77,312 KB
testcase_13 AC 56 ms
65,536 KB
testcase_14 AC 64 ms
68,992 KB
testcase_15 AC 112 ms
78,080 KB
testcase_16 AC 58 ms
66,560 KB
testcase_17 AC 42 ms
55,552 KB
testcase_18 AC 43 ms
55,168 KB
testcase_19 AC 54 ms
64,512 KB
testcase_20 AC 520 ms
81,280 KB
testcase_21 AC 526 ms
81,152 KB
testcase_22 AC 459 ms
79,492 KB
testcase_23 AC 929 ms
80,896 KB
testcase_24 AC 1,433 ms
260,620 KB
testcase_25 AC 855 ms
258,068 KB
testcase_26 AC 1,272 ms
260,628 KB
testcase_27 AC 180 ms
89,472 KB
testcase_28 AC 229 ms
101,408 KB
testcase_29 AC 190 ms
110,900 KB
testcase_30 AC 165 ms
94,964 KB
testcase_31 AC 906 ms
228,968 KB
testcase_32 AC 132 ms
76,800 KB
testcase_33 AC 258 ms
124,284 KB
testcase_34 AC 73 ms
76,032 KB
testcase_35 AC 74 ms
75,904 KB
testcase_36 AC 66 ms
75,904 KB
testcase_37 AC 82 ms
76,800 KB
testcase_38 AC 83 ms
76,032 KB
testcase_39 AC 69 ms
73,472 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Binary_Trie:
    """ Reference
    https://judge.yosupo.jp/submission/35057
    https://judge.yosupo.jp/submission/53782
    """

    def __init__(self, max_value, allow_multiple=False, query_number=None):
        self.bit=max_value.bit_length()
        self.upper=1<<self.bit
        self.multi=allow_multiple

        if query_number!=None:
            self.arc=[-1]*2*self.bit*(query_number+1)
            self.size=[0]*self.bit*(query_number+1)
            self.terminal=[0]*self.bit*(query_number+1)
            self.id=0
        else:
            self.arc=[-1,-1]
            self.size=[0]
            self.terminal=[0]

        self.query_number=query_number
        self.v_list=[0]*(self.bit+1)
        self.lazy_xor=0

    def xor_all(self, x):
        assert 0<=x<self.upper
        self.lazy_xor^=x

    def __ixor__(self, x):
        self.xor_all(x)
        return self

    def insert(self, x):
        """ x を追加する. """

        assert 0<=x<self.upper

        x^=self.lazy_xor
        v=0
        for i in reversed(range(self.bit)):
            d=(x>>i)&1
            if self.arc[2*v+d]==-1:
                if self.query_number!=None:
                    self.id+=1
                    self.arc[2*v+d]=self.id
                else:
                    self.arc[2*v+d]=len(self.size)
                    self.arc.append(-1); self.arc.append(-1)
                    self.terminal.append(0)
                    self.size.append(0)

            v=self.arc[2*v+d]
            self.v_list[i]=v

        if self.multi or self.terminal[v]==0:
            self.terminal[v]+=1
            for w in self.v_list:
                self.size[w]+=1

    def discard(self, x):
        """ x が存在する場合, x を削除する. """

        if not (0<=x<self.upper):
            return

        x^=self.lazy_xor
        v=0
        for i in reversed(range(self.bit)):
            d=(x>>i)&1
            if self.arc[2*v+d]==-1:
                return

            v=self.arc[2*v+d]
            self.v_list[i]=v

        if self.terminal[v]>0:
            self.terminal[v]-=1
            for w in self.v_list:
                self.size[w]-=1

    def erase(self, x, k):
        """ x を高々 k 回削除する (ただし, k=-1 のときは無限回)"""

        assert -1<=k
        if not (0<=x<self.upper):
            return

        x^=self.lazy_xor
        v=0
        for i in reversed(range(self.bit)):
            d=(x>>i)&1
            if self.arc[2*v+d]==-1:
                return

            v=self.arc[2*v+d]
            self.v_list[i]=v

        if (k==-1) or (self.terminal[v]<k):
            k=self.terminal[v]

        if self.terminal[v]>0:
            self.terminal[v]-=k
            for w in self.v_list:
                self.size[w]-=k

    def count(self, x):
        """ x の個数を求める. """
        if not (0<=x<self.upper):
            return 0

        x^=self.lazy_xor
        v=0
        for i in reversed(range(self.bit)):
            d=(x>>i)&1
            if self.arc[2*v+d]==-1:
                return 0
            v=self.arc[2*v+d]
        return self.terminal[v]

    def __contains__(self, x):
        return bool(self.count(x))

    def __len__(self):
        return self.size[0]

    def __bool__(self):
        return bool(len(self))

    def less_count(self, x, equal=False):
        """ x 未満の要素数を求める (equal=True のときは, "未満" が "以下" になる)"""

        x^=self.lazy_xor
        if equal:
            x+=1

        if x<0:
            return 0

        if self.upper<=x:
            return len(self)

        v=0
        res=0
        for i in reversed(range(self.bit)):
            d=(x>>i)&1
            lc=self.arc[2*v]
            rc=self.arc[2*v+1]

            if (self.lazy_xor>>i)&1:
                lc,rc=rc,lc

            if d:
                if lc!=-1:
                    res+=self.size[lc]
                if rc==-1:
                    return res
                v=rc
            else:
                if lc==-1:
                    return res
                v=lc
        return res

    def more_count(self, x, equal=False):
        """ x より大きい要素数を求める (equal=True のときは, "より大きい" が "以上" になる)"""

        return len(self)-self.less_count(x,not equal)

    def low_value(self, x, equal=False, default=None):
        """ x 未満の整数のうち, 最大の整数を求める (存在しない場合は default).

        equal: True のとき, "未満" が "以下" になる.
        """

        x^=self.lazy_xor
        if equal:
            x+=1

        alpha=self.less_count(x,False)
        if alpha==0:
            return default
        else:
            return self.kth_element(alpha,1)

    def high_value(self, x, equal=False, default=None):
        """ x より大きい整数のうち, 最小の整数を求める (存在しない場合は default)

        equal: True のとき, "より大きい" が "以上" になる.
        """

        x^=self.lazy_xor
        if equal:
            x-=1

        beta=self.more_count(x,False)
        if beta==0:
            return default
        else:
            return self.kth_element(-beta,0)

    def kth_element(self, k, index=0, default=-1):
        """ index -indexed で k 番目に小さい値を求める.
        ただし, index=0, k<0 のときは |k| 番目に大きい値になる.

        """

        if k<0:
            k+=self.size[0]
        k-=index
        if not (0<=k<self.size[0]):
            return default

        v=0
        res=0
        for i in reversed(range(self.bit)):
            lc=self.arc[2*v]
            rc=self.arc[2*v+1]

            if (self.lazy_xor>>i)&1:
                lc,rc=rc,lc

            if lc==-1:
                v=rc
                res|=1<<i
            elif self.size[lc]<=k:
                k-=self.size[lc]
                v=rc
                res|=1<<i
            else:
                v=lc
        return res

    def get_min(self):
        return self.kth_element(1,1)

    def get_max(self):
        return self.kth_element(-1)

    def get_median(self, mode=0, func=None):
        """ 中央値を求める.

        [mode] 項の数が偶数のときの中央値の求め方を指定する (その 2値を a,b (a<=b) とする).
        mode=-1 → a
        mode= 0 → (a+b)/2 (float 型)
        mode= 1 → b
        mode=(その他) → その他 ( 2変数関数 func(a,b) で指定)
        """

        if len(self)%2==1:
            return self.kth_element(len(self)//2)
        else:
            a=self.kth_element(len(self)//2)
            b=self.kth_element(len(self)//2-1)

            if mode==-1:
                return a
            elif mode==1:
                return b
            elif mode==0:
                return (a+b)/2
            else:
                return func(a,b)

    def __getitem__(self, index):
        return self.kth_element(index)

#==================================================
def solve():
    from operator import itemgetter
    from collections import defaultdict

    N,K,L,P=map(int,input().split())
    A=[0]*N; B=[0]*N
    for i in range(N):
        A[i],B[i]=map(int,input().split())

    def bit(x,k):
        return (x>>k)&1

    def calc(C,D):
        T=[defaultdict(list) for _ in range(K+1)]

        N=len(C)
        for S in range(1<<N):
            cost=0; value=0; count=0
            for i in range(N):
                if bit(S,i):
                    cost+=C[i]
                    count+=1
                    value+=D[i]

            if cost<=L and count<=K:
                T[count][cost].append(value)

        return [sorted(T[k]) for k in range(K+1)], T

    F0,G0=calc(A[:N//2], B[:N//2])
    F1,G1=calc(A[N//2:], B[N//2:])

    T=[Binary_Trie(4*10**10, True) for _ in range(K+1)]
    for k in range(K+1):
        t=T[k]
        for c in F1[k]:
            for w in G1[k][c]:
                t.insert(w)
    F=[]
    for k in range(K+1):
        F.extend([(cost,k) for cost in F0[k]])
    F.sort(key=itemgetter(0))

    X=0
    for cost,k in F:
        for r in range(K+1):
            while F1[r] and cost+F1[r][-1]>L:
                for w in G1[r][F1[r][-1]]:
                    T[r].discard(w)
                F1[r].pop()

            if k+r<=K:
                for value in G0[k][cost]:
                    X+=T[r].more_count(max(0, P-value), True)
    return X

#==================================================
print(solve())
0