結果

問題 No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
コンテスト
ユーザー まぬお
提出日時 2026-01-23 22:53:44
言語 PyPy3
(7.3.17)
結果
TLE  
実行時間 -
コード長 3,415 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 386 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 173,760 KB
最終ジャッジ日時 2026-01-23 22:54:29
合計ジャッジ時間 32,946 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 3 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations
from heapq import heappop, heappush
import math, sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
_int = lambda x: int(x)-1
MOD = 998244353 #10**9+7
INF = 1<<60
Yes, No = "Yes", "No"

class FenwickTree:
    '''Reference: https://en.wikipedia.org/wiki/Fenwick_tree'''

    def __init__(self, n: int = 0) -> None:
        self._n = n
        self.data = [0] * n

    def add(self, p: int, x) -> None:
        assert 0 <= p < self._n

        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, left: int, right: int):
        assert 0 <= left <= right <= self._n

        return self._sum(right) - self._sum(left)

    def _sum(self, r: int):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r

        return s

for _ in range(int(input())):
    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()))

    Y = set()
    KA = [[] for _ in range(K)]
    for i in range(N):
        KA[C[i]-1].append(i)
        Y.add(T[i])
        Y.add(T[i]-S[C[i]-1])
    KB = [[] for _ in range(K)]
    for i in range(M):
        KB[D[i]-1].append(B[i])
        Y.add(B[i])
    X = sorted(list(Y))
    pos = {x: e for e, x in enumerate(X)}
    posa = [0]*N
    for i in range(N): posa[i] = pos[T[i]]
    possa = [0]*N
    for i in range(N): possa[i] = pos[T[i]-S[C[i]-1]]
    posb = [0]*M
    for i in range(M): posb[i] = pos[B[i]]
    L = len(X)

    def check(m):
        F = FenwickTree(L)
        for i in range(N): F.add(posa[i], 1)
        ret = 0
        for i in range(K):
            for ai in KA[i]:
                F.add(posa[ai], -1)
                F.add(possa[ai], 1)
            for b in KB[i]:
                j = bisect_right(X, m-b)
                ret += F.sum(0, j)
            for ai in KA[i]:
                F.add(possa[ai], -1)
                F.add(posa[ai], 1)
        return ret < P
    
    def calc(m):
        F1 = FenwickTree(L)
        for i in range(N): F1.add(posa[i], 1)
        F2 = FenwickTree(L)

        ok = False
        for i in range(K):
            for ai in KA[i]:
                F1.add(posa[ai], -1)
                F2.add(possa[ai], 1)
            for b in KB[i]:
                j = pos.get(m-b, -1)
                if j < 0: continue
                if F1.sum(j, j+1):
                    reta = m-b
                    retb = b
                elif F2.sum(j, j+1):
                    reta = m-b+S[i]
                    retb = b
                else: continue
                ok = True
            if ok: break
            for ai in KA[i]:
                F2.add(possa[ai], -1)
                F1.add(posa[ai], 1)
        # print(reta, retb)
        for i in range(N):
            if reta == T[i]:
                resi = i+1
                break
        for j in range(M):
            if retb == B[j]:
                resj = j+1
                break
        return resi, resj

    l, r = -1, 3*(10**9)
    while r-l > 1:
        m = (l+r)//2
        if check(m): l = m
        else: r = m
    # print(l, r)
    ans = calc(r)
    print(*ans)
0