結果

問題 No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
コンテスト
ユーザー detteiuu
提出日時 2026-02-14 00:39:43
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 1,382 ms / 4,000 ms
コード長 2,748 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 398 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 150,784 KB
最終ジャッジ日時 2026-02-14 00:40:35
合計ジャッジ時間 44,039 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from sys import stdin
input = stdin.readline
from collections import defaultdict

def func(limit):
    ans = 0
    right = M-1
    l, r = -1, -1
    for left in range(N):
        while 0 <= right and limit < T[left]+B[right]:
            right -= 1
        if right == -1:
            break
        ans += right+1
    right = M-1
    for left in range(N):
        while 0 <= right and limit <= T[left]+B[right]:
            if (len(DT[T[left]]) == 2 or len(DT[T[left]]) == 1 and DT[T[left]][0][0] != D[idxB[right]]) and limit == T[left]+B[right] and l == -1:
                r = idxB[right]
                if DT[T[left]][0][0] != D[r]:
                    l = DT[T[left]][0][1]
                else:
                    l = DT[T[left]][1][1]
            right -= 1
        if right == -1:
            break
    for i in range(K):
        if len(F[i]) == 0:
            continue
        left = len(F[i])-1
        right = len(F[i])-1
        for j, e in enumerate(E[i]):
            while 0 <= right and limit+S[i] < e+F[i][right]:
                right -= 1
            while 0 <= left and limit < e+F[i][left]:
                left -= 1
            if right == -1:
                break
            ans += right-left
            if limit+S[i] == e+F[i][right] and l == -1:
                l, r = idxE[i][j], idxF[i][right]
    return ans, l, r

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()))

    DT = defaultdict(list)
    for i, t in enumerate(T):
        if t not in DT:
            DT[t].append((C[i], i))
        elif len(DT[t]) == 1 and DT[t][0][0] != C[i]:
            DT[t].append((C[i], i))

    E = [[] for _ in range(K)]
    idxE = [[] for _ in range(K)]
    F = [[] for _ in range(K)]
    idxF = [[] for _ in range(K)]
    for i in range(N):
        E[C[i]-1].append((T[i], i))
    for i in range(M):
        F[D[i]-1].append((B[i], i))
    for i in range(K):
        if E[i]:
            a, b = map(list, zip(*sorted(E[i], key=lambda x:x[0])))
            E[i] = a
            idxE[i] = b
        if F[i]:
            a, b = map(list, zip(*sorted(F[i], key=lambda x:x[0])))
            F[i] = a
            idxF[i] = b
    idxT, T = map(list, zip(*sorted(enumerate(T), key=lambda x:x[1])))
    idxB, B = map(list, zip(*sorted(enumerate(B), key=lambda x:x[1])))

    left = 0
    right = 10**10
    while left+1 < right:
        mid = (left+right)//2
        f, _, _ = func(mid)
        if f < P:
            left = mid
        else:
            right = mid
    
    _, l, r = func(right)
    print(l+1, r+1)
0