結果

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

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from bisect import bisect

Q=int(input())

for tests in range(Q):
    N,M,K,P=list(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()))

    SB=sorted(B)

    SC=[[] for i in range(N+M+1)]

    for i in range(M):
        b,d=B[i],D[i]
        SC[d].append(b)

    for i in range(N+M+1):
        SC[i].sort()

    OK=3*10**9
    NG=0

    while OK>NG+1:
        mid=(OK+NG)//2

        count=0

        for i in range(N):
            t=T[i]
            c=C[i]

            count+=bisect(SB,mid-t)

            count+=bisect(SC[c],mid+S[c-1]-t)
            count-=bisect(SC[c],mid-t)

        if count>=P:
            OK=mid
        else:
            NG=mid

    #print(OK)

    ind=-1

    for i in range(N):
        t=T[i]
        c=C[i]

        k=bisect(SC[c],OK+S[c-1]-t)
        if k>=1:
            if SC[c][k-1]==OK+S[c-1]-t:
                ind=i
                break

    if ind!=-1:
        t,c=T[ind],C[ind]

        for i in range(M):
            b,d=B[i],D[i]

            if c==d:
                if t+b-S[c-1]==OK:
                    ind2=i
                    break
            else:
                if t+b==OK:
                    ind2=i
                    break

        print(ind+1,ind2+1)
        continue

    ind=-1

    for i in range(N):
        t=T[i]
        c=C[i]

        ko1=bisect(SB,OK-t)-bisect(SB,OK-t-1)
        ko2=bisect(SC[c],OK-t)-bisect(SC[c],OK-t-1)

        if ko1>ko2:
            ind=i
            break

    if ind!=-1:
        t,c=T[ind],C[ind]

        for i in range(M):
            b,d=B[i],D[i]

            if c==d:
                if t+b-S[c-1]==OK:
                    ind2=i
                    break
            else:
                if t+b==OK:
                    ind2=i
                    break

        print(ind+1,ind2+1)
        continue
0