結果

問題 No.674 n連勤
ユーザー NoneNone
提出日時 2021-02-17 20:41:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 439 ms / 2,000 ms
コード長 9,413 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 104,312 KB
最終ジャッジ日時 2024-09-14 06:08:44
合計ジャッジ時間 4,116 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
54,168 KB
testcase_01 AC 41 ms
55,104 KB
testcase_02 AC 42 ms
53,984 KB
testcase_03 AC 43 ms
54,532 KB
testcase_04 AC 42 ms
55,200 KB
testcase_05 AC 43 ms
55,260 KB
testcase_06 AC 41 ms
55,608 KB
testcase_07 AC 42 ms
54,984 KB
testcase_08 AC 42 ms
54,600 KB
testcase_09 AC 41 ms
54,776 KB
testcase_10 AC 43 ms
54,052 KB
testcase_11 AC 121 ms
77,192 KB
testcase_12 AC 157 ms
78,396 KB
testcase_13 AC 143 ms
80,340 KB
testcase_14 AC 165 ms
104,296 KB
testcase_15 AC 199 ms
99,084 KB
testcase_16 AC 357 ms
104,108 KB
testcase_17 AC 359 ms
104,216 KB
testcase_18 AC 439 ms
98,280 KB
testcase_19 AC 198 ms
104,312 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#####################################################################################################
##### SortedInterval
#####################################################################################################
"""

10^5個の区間まで間に合う

ベンチマーク
	No.674 n連勤: https://yukicoder.me/submissions/617927

"""


class Bit:

    __slots__ = ["n","tree","depth"]

    def __init__(self,n):
        """
        :param n: number of elements
        """
        self.n=n
        self.tree=[0]*(n+1)
        self.depth=n.bit_length()-1

    def sum(self,i):
        """ return summation of elements in [0,i) """
        s=0
        i-=1
        while i>=0:
            s+=self.tree[i]
            i=(i&(i+1))-1
        return s

    def build(self,array):
        """ bulid BIT from array """
        for i,a in enumerate(array):
            self.add(i,a)

    def add(self,i,x):
        """ add x to i-th element """
        while i<self.n:
            self.tree[i]+=x
            i|=i+1

    def get(self,i,j):
        """ return summation of elements in [i,j) """
        if i==0:
            return self.sum(j)
        return self.sum(j)-self.sum(i)

    def lower_bound(self,x,equal=False):
        """
        return tuple = (return maximum i s.t. a0+a1+...+ai < x (if not existing, -1 ) , a0+a1+...+ai )
        if one wants to include equal (i.e., a0+a1+...+ai <= x), please set equal = True
        (Cation) We must assume that A_i>=0
        """
        sum_=0
        pos=-1  # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<self.n and sum_+self.tree[k]<x:  # 1-indexed の時は k <= self.n
                    sum_+=self.tree[k]
                    pos+=1<<i
        if equal:
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<self.n and sum_+self.tree[k]<=x:  # 1-indexed の時は k <= self.n
                    sum_+=self.tree[k]
                    pos+=1<<i
        return pos,sum_

    def __getitem__(self,i):
        """ [a0, a1, a2, ...] """
        if i<0: i=self.n+i
        return self.get(i,i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i,i+1)

    def __str__(self):
        text1=" ".join(["element:            "]+list(map(str,self)))
        text2=" ".join(["cumsum(1-indexed):  "]+list(str(self.sum(i)) for i in range(1,self.n+1)))
        return "\n".join((text1,text2))


class SortedList2:
    """ if we need compress """

    __slots__=["data","n","size","flip","code","decode","p"]

    def __init__(self,data,A=[]):
        """
        self.size: number of elements in BitSet
        """
        self.data=sorted(list(set(data)))
        self.n=len(self.data)
        self.p=Bit(self.n+1)
        self.size=0
        self.flip=0
        self.code={}
        self.decode=[]
        for i,b in enumerate(self.data):
            self.code[b]=i
            self.decode.append(b)
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(self.code[x],1)
        self.size+=1
        self.flip+=self.size-self.p.sum(self.code[x]+1)  # we can remove this if we do not use flip_number

    def remove(self,x):
        self.p.add(self.code[x],-1)
        self.size-=1

    def bisect_left(self,x):
        """ return bisect_left(sorted(B),x) """
        if x in self.code.keys():
            return self.p.sum(self.code[x])
        else:
            return self.p.sum(bisect_right(self.data,x))

    def bisect_right(self,x):
        """ return bisect_right(sorted(B),x) """
        x+=1
        if x in self.code.keys():
            return self.p.sum(self.code[x])
        else:
            return self.p.sum(bisect_right(self.data,x))

    def count(self,x):
        return self.p[self.code[x]]

    def count_range(self,l,r):
        """ return number of elements in closed set [l,r]"""
        return self.bisect_right(r)-self.bisect_left(l)

    def minimum(self,k=1):
        """ return k-th minimum value """
        if k<=self.size:
            return self.decode[self.p.lower_bound(k)[0]+1]
        else:
            sys.stderr.write("minimum: list index out of range (k={0})\n".format(k))

    def min(self):
        return self.minimum(1)

    def max(self):
        return self.decode[self.p.lower_bound(self.size)[0]+1]

    def upper_bound(self,x,equal=False):
        """ return maximum element lower than x """
        if x in self.code.keys():
            y=self.code[x]+equal
        else:
            y=bisect_right(self.data,x)
        k=self.p.sum(y)
        if k:
            return self.minimum(k)

    def lower_bound(self,x,equal=False):
        """ return minimum element greater than x """
        if x in self.code.keys():
            y=self.code[x]+1-equal
        else:
            y=bisect_left(self.data,x)
        k=self.p.sum(y)+1
        if k<=self.size:
            return self.minimum(k)

    def nearest(self,x,k):
        """ return k-th nearest value to x """
        if k>len(self):
            sys.stderr.write("nearest: k (= {0}) is larger than the size of this BitSet\n".format(k))
            return

        def test(d):
            r=self.bisect_right(x+d)-1
            l=self.bisect_left(x-d)
            return r-l+1<=k

        ok,ng=0,10**18+1
        while abs(ok-ng)>1:
            mid=(ok+ng)//2
            if test(mid):
                ok=mid
            else:
                ng=mid
        d=ok

        r=self.bisect_right(x+d)-1
        l=self.bisect_left(x-d)
        if d==0:
            R=self.lower_bound(x,equal=True)
            L=self.upper_bound(x,equal=True)
            if abs(x-L)==abs(R-x):
                if self.count(L)>=k:
                    return L
                else:
                    return R
            elif abs(x-L)<abs(R-x):
                return L
            else:
                return R
        elif r-l+1==k:
            R=self[r]
            L=self[l]
            if abs(x-L)<=abs(R-x):
                return R
            else:
                return L
        else:
            if l<=0:
                return self[r+1]
            elif r>=len(self)-1:
                return self[l-1]
            else:
                R=self[r+1]
                L=self[l-1]
                if abs(x-L)==abs(R-x):
                    if self.count(L)>=k-(r-l+1):
                        return L
                    else:
                        return R
                elif abs(x-L)<abs(R-x):
                    return L
                else:
                    return R

    def __getitem__(self,k):
        """
        return k-th minimum element (0-indexed)
        B[k] = sorted(A)[k]
        """
        if len(self)==0:
            sys.stderr.write("__getitem__: no elements exist in this BitSet\n")
        elif k>=len(self):
            sys.stderr.write(
                "__getitem__: index (={0}) is larger than the maximum index (={1})\n".format(k,len(self)-1))
        elif k>=0:
            return self.minimum(k+1)
        else:
            sys.stderr.write("__getitem__: index (={0}) is negative \n".format(k))

    def __len__(self):
        return self.size

    def __iter__(self):
        """ return sorted list """
        for i in range(self.n+1):
            if self.p[i]:
                for _ in range(self.p[i]):
                    yield self.decode[i]

    def __str__(self):
        """ return sorted list """
        text1=" ".join(list(map(str,self)))
        return "["+text1+"]"


class SortedInterval:

    __slots__ = ["SL","rs","length"]
    def __init__(self,data):
        self.SL=SortedList2(data)
        self.rs={}
        self.length=0

    def add(self,l,r):

        prev_l=self.SL.upper_bound(l)
        if prev_l is not None and l<=self.rs[prev_l]:
            l=prev_l
            r=max2(r,self.rs[prev_l])
            del self.rs[prev_l]
            self.SL.remove(prev_l)
        removed=[]
        next_l=self.SL.lower_bound(l,equal=True)
        while next_l is not None and next_l<=r:
            removed.append(next_l)
            next_l=self.SL.lower_bound(next_l)
        for next_l in removed:
            r=max2(r,self.rs[next_l])
            del self.rs[next_l]
            self.SL.remove(next_l)
        self.SL.add(l)
        self.rs[l]=r
        # 新しく生成された区間の大きさを返す
        return r-l

    def sum(self):
        res=0
        for l in self.SL:
            res+=self.rs[l]-l+1
        return res

    def __iter__(self):
        for l in self.SL:
            yield l,self.rs[l]


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


#########################################################
def example():
    global input
    example=iter(
        """
30 12
10 10
15 15
10 11
14 15
14 16
9 11
12 14
13 17
19 29
13 18
11 29
0 13
        """
            .strip().split("\n"))
    input=lambda:next(example)


#########################################################
import sys

input=sys.stdin.readline
from bisect import bisect_left,bisect_right

# example()

N,Q=map(int,input().split())
intervals=[]
data=[]
for _ in range(Q):
    l,r=map(int,input().split())
    intervals.append((l,r))
    data.append(l)
    data.append(r+1)

SI=SortedInterval(data)
ans=0
for l,r in intervals:
    ans=max(SI.add(l,r+1),ans)
    print(ans)
0