結果

問題 No.817 Coin donation
コンテスト
ユーザー None
提出日時 2021-03-04 22:22:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 324 ms / 2,000 ms
コード長 3,317 bytes
コンパイル時間 411 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 148,460 KB
最終ジャッジ日時 2024-10-05 11:36:48
合計ジャッジ時間 3,179 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Imos:
    def __init__(self,decrement=1):
        self.decode=set()
        self.data=[]
        self.idx=decrement

    def update_range(self,l,r,k):
        """ update elems in [l,r) """
        data,decode=self.data,self.decode
        l, r = l-self.idx, r-self.idx
        data.append((l,r,k))
        decode.add(l)
        decode.add(r)


    def simulate(self):
        data,decode=self.data,self.decode
        decode=self.decode=sorted(list(decode))
        code=self.code={e:i for i,e in enumerate(decode)}
        N=self.N=len(self.decode)
        imos=[0]*N
        acc=[0]

        for l,r,k in data:
            l,r=code[l],code[r]
            imos[l]+=k
            imos[r]-=k

        for s in imos:
            acc.append(acc[-1]+s)
        self.acc=acc[1:]

    def get(self,x):
        acc,decode=self.acc,self.decode
        x=x-self.idx
        return acc[bisect_right(decode,x)-1]

    def get_range(self,l,r):
        """
        sum elems in [l,r)
        計算量: O(N) ; N=number of updates
        備考: 区間取得をO(1)でするならば、遅延セグ木が必要
        """
        def f(x):
            """ 累積後の各要素への作用 """
            return x

        acc,decode,code=self.acc,self.decode,self.code
        l,r=l-self.idx,r-self.idx
        il,ir=bisect_right(decode,l)-1, bisect_right(decode,r)-1
        res=0
        res+=(decode[il+1]-l)*f(acc[il])
        for i in range(il+1,ir):
            """
            座圧で全ての区間をサイズ１にしたので、 
            (decode[i+1]-decode[i])を掛けて元に戻している
            区間内では全ての要素が同じ値を持つので、
            単純にacc[i]を(decode[i+1]-decode[i])倍するだけでよい
            """
            res+=(decode[i+1]-decode[i])*f(acc[i])
        res+=(r-decode[ir])*f(acc[ir])
        return res

    def get_all_range(self):
        return self.get_range(self.idx, self.decode[-1]+1+self.idx)

    def __getitem__(self, x):
        acc,decode=self.acc,self.decode
        x=x-self.idx
        return acc[bisect_right(decode,x)-1]

    def __iter__(self):
        for i in range(self.decode[-1]):
            yield self.get(i+self.idx)

    def __str__(self):
        return str(list(self))

def max2(x,y):
    return x if x > y else y


def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

#########################################################
def example():
    global input
    example = iter(
        """
10 3
1 5
4 8
12 14
        """
            .strip().split("\n"))
    input = lambda: next(example)
#########################################################
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

# example()

N,K=map(int, input().split())
imos=Imos(decrement=1)
for _ in range(N):
    l, r = map(int, input().split())    # 区間は閉区間 [l,r] で与えられる
    imos.update_range(l,r+1,1)

imos.simulate()

def test(x):
    return imos.get_range(0,x)<K



res=binary_search_int(0,10**18,test)

print(res)
0