結果

問題 No.3166 [Cherry 7th Tune *] 桜の守人
コンテスト
ユーザー 👑 Kazun
提出日時 2023-10-22 18:40:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 660 ms / 2,000 ms
コード長 2,335 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 81,852 KB
実行使用メモリ 156,576 KB
最終ジャッジ日時 2025-05-30 21:02:40
合計ジャッジ時間 15,189 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

def General_Binary_Increase_Search_Integer(L, R, cond, default=None):
    """ 条件式が単調増加であるとき, 整数上で二部探索を行う.

    L: 解の下限
    R: 解の上限
    cond: 条件(1変数関数, 広義単調増加を満たす)
    default: Lで条件を満たさないときの返り値
    """

    if not(cond(R)):
        return default

    if cond(L):
        return L

    R+=1
    while R-L>1:
        C=L+(R-L)//2
        if cond(C):
            R=C
        else:
            L=C
    return R

from collections import defaultdict
class Sparse_Imos_1:
    def __init__(self):
        self.dict=defaultdict(int)

    def add(self, l, r, x=1):
        """閉区間 [l,r] に x を加算する.
        """

        if l<=r:
            self.dict[l]+=x
            self.dict[r+1]-=x

    def cumulative_sum(self, since, until):
        """累積和を求める.

        [Output]
        (y, l, r) という形のリスト. ただし, (y, l, r) は l<=x<=y の範囲では y であるということを意味する.
        """
        Y=[]
        S=0
        t_old=since
        dic=self.dict
        for t in sorted(dic):
            if t>until:
                break
            if dic[t]==0:
                continue

            if t_old<=t-1:
                Y.append((S, t_old,t-1))

            S+=dic[t]
            t_old=t

        if t_old<=until:
            Y.append((S, t_old,until))
        return Y

#==================================================
def solve():
    N, L, K = map(int, input().split())
    X = list(map(int, input().split()))

    def check(P):
        if 2 * P > L:
            return True

        I = Sparse_Imos_1()
        for x in X:
            if x - P < 0:
                I.add(0, x + P - 1)
                I.add((x - P) + L, L - 1)
            elif L - 1 < x + P - 1:
                I.add(0, x + P - L - 1)
                I.add(x - P, L - 1)
            else:
                I.add(x - P, x + P - 1)

        J = I.cumulative_sum(0, L - 1)
        return min(y for y, _, _ in J) >= K

    return General_Binary_Increase_Search_Integer(0, (L + 1) // 2, check, -1)

#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write

T = int(input())
write("\n".join(map(str, [solve() for _ in range(T)])))
0