#1176256 (PyPy3) No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?

• 問題: No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
• ユーザー: LyricalMaestro
• 提出日時: 2026-08-11 18:18:39
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 3,016 ms / 4,000 ms
• コード長: 5,693 bytes
• コンパイル時間: 1,337 ms
• コンパイル使用メモリ: 95,912 KB
• 実行使用メモリ: 156,936 KB
• 最終ジャッジ日時: 2026-08-11 18:20:29
• 合計ジャッジ時間: 79,220 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 43

ソースコード

# https://yukicoder.me/problems/no/3436

class BinaryIndexTree:
    """
    フェニック木(BinaryIndexTree)の基本的な機能を実装したクラス
    """
    def __init__(self, size):
        self.size = size
        self.array = [0] * (size + 1)
    
    def add(self, x, a):
        index = x
        while index <= self.size:
            self.array[index] += a
            index += index & (-index)
    
    def sum(self, x):
        index = x
        ans = 0
        while index > 0:
            ans += self.array[index]
            index -= index & (-index)
        return ans

    def least_upper_bound(self, value):
        if self.sum(self.size) < value:
            return -1
        elif value <= 0:
            return 0

        m = 1
        while m < self.size:
            m *= 2

        k = 0
        k_sum = 0
        while m > 0:
            k0 = k + m
            if k0 < self.size:
                if k_sum + self.array[k0] < value:
                    k_sum += self.array[k0]
                    k += m
            m //= 2
        if k < self.size:
            return k + 1
        else:
            return -1


def count_lower(t_color_map, B, D, S, bit, b_list, b_map, b_color_map, value):
    count = 0
    for target_color, t_array in t_color_map.items():
        if target_color in b_color_map:
            for j in b_color_map[target_color]:
                b_ = b_map[B[j]]
                bit.add(b_, -1)
                b_ = b_map[B[j] - S[D[j] - 1]]
                bit.add(b_, 1)

        for t, _ in t_array:
            t0 = value - t

            # b_list の中でどれくらいのランクにいるか？
            if t0 < b_list[0]:
                continue

            low = 0
            high = len(b_list) - 1
            while high - low > 1:
                mid = (high + low) // 2
                if b_list[mid] <= t0:
                    low = mid
                else:
                    high = mid
            if b_list[high] <= t0:
                v = high
            else:
                v = low
            count += bit.sum(v + 1)

        if target_color in b_color_map:
            for j in b_color_map[target_color]:
                b_ = b_map[B[j]]
                bit.add(b_, 1)
                b_ = b_map[B[j] - S[D[j] - 1]]
                bit.add(b_, -1)
    return count


def solve(N, M, K, P, T, C, B, D, S):
    # ボトムス側の値の準備
    b_set = set()
    for j in range(M):
        b = B[j]
        s = S[D[j] - 1]
        b_set.add(b)
        b_set.add(b - s)
    b_list = list(b_set)
    b_list.sort()
    b_map = {}
    for i, b in enumerate(b_list):
        b_map[b] = i + 1

    bit = BinaryIndexTree(len(b_list))
    b_color_map = {}
    for j in range(M):
        b = B[j]
        d = D[j]
        if d not in b_color_map:
            b_color_map[d] = []
        b_color_map[d].append(j)
        bit.add(b_map[b], 1)

    # トップスの準備
    t_color_map = {}
    for i in range(N):
        t = T[i]
        c = C[i]
        if c not in t_color_map:
            t_color_map[c] = []
        t_color_map[c].append((t, i))

    # 対象のコストを計算
    low = 0
    high = max(T) + max(B)
    while high - low > 1:
        mid = (high + low) // 2
        if count_lower(t_color_map, B, D, S, bit, b_list, b_map, b_color_map, mid) >= P:
            high = mid
        else:
            low = mid
    if count_lower(t_color_map, B, D, S, bit, b_list, b_map, b_color_map, low) >= P:
        target_value = low
    else:
        target_value = high

    # ボトムスの準備
    b_value_map = {}
    for j in range(M):
        b = B[j]
        if b not in b_value_map:
            b_value_map[b] = set()
        b_value_map[b].add(j)

    # 対象のコストとなり得る組み合わせをチョイス
    for target_color, t_array in t_color_map.items():
        if target_color in b_color_map:
            for j in b_color_map[target_color]:
                b = B[j]
                b_value_map[b].remove(j)
                b = B[j] - S[D[j] - 1]
                if b not in b_value_map:
                    b_value_map[b] = set()
                b_value_map[b].add(j)

        for t, t_index in t_array:
            target_b_value = target_value - t
            if target_b_value in b_value_map:
                if len(b_value_map[target_b_value]) > 0:
                    return t_index + 1, list(b_value_map[target_b_value])[0] + 1

        if target_color in b_color_map:
            for j in b_color_map[target_color]:
                b = B[j] - S[D[j] - 1]
                b_value_map[b].remove(j)
                b = B[j]
                if b not in b_value_map:
                    b_value_map[b] = set()
                b_value_map[b].add(j)


def solve2(N, M, K, P, T, C, B, D, S):
    array = []
    for i in range(N):
        t = T[i]
        c = C[i]
        for j in range(M):
            b = B[j]
            val = t + b
            if c == D[j]:
                val -= S[c - 1]
            array.append((i + 1, j + 1, val))
    array.sort(key=lambda x: x[2])

    i, j, val = array[P - 1]
    print(i, j, val)


def main():
    Q = int(input())
    answers = []
    for _ in range(Q):
        N, M, K, P = map(int, input().split())
        T= list(map(int, input().split()))
        C= list(map(int, input().split()))
        B= list(map(int, input().split()))
        D= list(map(int, input().split()))
        S= list(map(int, input().split()))
        ans = solve(N, M, K, P, T, C, B, D, S)
        answers.append(ans)
#        solve2(N, M, K, P, T, C, B, D, S)

    for ans in answers:
        print(ans[0], ans[1])






if __name__ == "__main__":
    main()