結果

問題 No.674 n連勤
ユーザー NoneNone
提出日時 2021-02-14 18:50:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 427 ms / 2,000 ms
コード長 7,594 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 81,808 KB
実行使用メモリ 104,576 KB
最終ジャッジ日時 2024-07-22 05:32:21
合計ジャッジ時間 4,004 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
53,760 KB
testcase_01 AC 45 ms
53,760 KB
testcase_02 AC 47 ms
53,504 KB
testcase_03 AC 46 ms
53,376 KB
testcase_04 AC 45 ms
53,760 KB
testcase_05 AC 46 ms
53,248 KB
testcase_06 AC 45 ms
53,504 KB
testcase_07 AC 45 ms
53,248 KB
testcase_08 AC 45 ms
53,248 KB
testcase_09 AC 47 ms
53,504 KB
testcase_10 AC 45 ms
53,120 KB
testcase_11 AC 113 ms
77,312 KB
testcase_12 AC 164 ms
77,696 KB
testcase_13 AC 151 ms
80,384 KB
testcase_14 AC 173 ms
104,320 KB
testcase_15 AC 210 ms
98,560 KB
testcase_16 AC 360 ms
104,576 KB
testcase_17 AC 358 ms
104,320 KB
testcase_18 AC 427 ms
97,792 KB
testcase_19 AC 212 ms
104,448 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Bit:
    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 """
    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.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

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

    def order(self,x):
        """
        return x rank in order of decreasing(1-indexed)
        BIT.order(x) = bisect_left(BIT.sort(),x) + 1
        BIT.minimum(BIT.order(x)) = BIT.lower_bound(x)
        """
        if x in self.code.keys():
            return self.p.sum(self.code[x]) + 1
        else:
            return self.p.sum(bisect_right(self.data, x)) + 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 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-1)
        k = self.p.sum(y) + 1
        if k <= self.size:
            return self.minimum(k)

    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:
    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