結果

問題 No.674 n連勤
ユーザー neterukunneterukun
提出日時 2021-02-14 15:15:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 661 ms / 2,000 ms
コード長 6,528 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 95,120 KB
最終ジャッジ日時 2024-07-21 23:39:17
合計ジャッジ時間 4,705 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,888 KB
testcase_01 AC 39 ms
53,504 KB
testcase_02 AC 39 ms
53,760 KB
testcase_03 AC 40 ms
54,016 KB
testcase_04 AC 40 ms
54,016 KB
testcase_05 AC 41 ms
53,888 KB
testcase_06 AC 39 ms
53,248 KB
testcase_07 AC 39 ms
53,632 KB
testcase_08 AC 39 ms
53,632 KB
testcase_09 AC 39 ms
53,632 KB
testcase_10 AC 39 ms
53,504 KB
testcase_11 AC 108 ms
77,544 KB
testcase_12 AC 163 ms
78,460 KB
testcase_13 AC 158 ms
80,664 KB
testcase_14 AC 150 ms
80,512 KB
testcase_15 AC 206 ms
81,360 KB
testcase_16 AC 598 ms
95,120 KB
testcase_17 AC 581 ms
93,444 KB
testcase_18 AC 661 ms
91,500 KB
testcase_19 AC 147 ms
80,512 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left, bisect_right, insort


class BTreeNode:
    def __init__(self, B_SIZE):
        self.B_SIZE = B_SIZE
        self.keys = []
        self.children = []

    def split(self):
        if len(self.keys) != self.B_SIZE * 2:
            return None
        ptr = BTreeNode(self.B_SIZE)
        ptr.keys, self.keys = self.keys[:self.B_SIZE], self.keys[self.B_SIZE:]
        ptr.children, self.children = self.children[:self.B_SIZE], self.children[self.B_SIZE:]
        return ptr

    def shift_lr(self, idx):
        ptrl, ptrr = self.children[idx], self.children[idx + 1]
        ptrr.keys.insert(0, ptrl.keys[-1])
        del ptrl.keys[-1]
        if ptrl.children:
            ptrr.children.insert(0, ptrl.children[-1])
            del ptrl.children[-1]
        self.keys[idx], ptrr.keys[0] = ptrr.keys[0], self.keys[idx]

    def shift_rl(self, idx):
        ptrl, ptrr = self.children[idx], self.children[idx + 1]
        ptrl.keys.append(ptrr.keys[0])
        del ptrr.keys[0]
        if ptrr.children:
            ptrl.children.append(ptrr.children[0])
            del ptrr.children[0]
        self.keys[idx], ptrl.keys[-1] = ptrl.keys[-1], self.keys[idx]

    def merge(self, idx):
        self.children[idx].keys += [self.keys[idx]] + self.children[idx + 1].keys
        self.children[idx].children += self.children[idx + 1].children
        del self.keys[idx], self.children[idx + 1]
        assert(len(self.keys) + 1 == len(self.children))


class SortedSetBTree:
    def __init__(self, B_SIZE=512):
        self.B_SIZE = B_SIZE
        self.root = BTreeNode(self.B_SIZE)
        self.size = 0

    def __contains__(self, key):
        return self._search(key)

    def __len__(self):
        return self.size

    def __iter__(self):
        return self._generate_rec(self.root)

    def _search(self, key):
        ptr = self.root
        while True:
            idx = bisect_left(ptr.keys, key)
            if idx != len(ptr.keys) and ptr.keys[idx] == key:
                return True
            if not ptr.children:
                return False
            ptr = ptr.children[idx]

    def _generate_rec(self, ptr):
        for idx, chi in enumerate(ptr.children):
            yield from self._generate_rec(chi)
            if idx < len(ptr.keys):
                yield ptr.keys[idx]
        if not ptr.children:
            for key in ptr.keys:
                yield key

    def _generate_rec_kl(self, ptr, kl, f):
        idxl = 0 if f else bisect_left(ptr.keys, kl)
        for idx, chi in enumerate(ptr.children[idxl:], idxl):
            if idx == idxl:
                yield from self._generate_rec_kl(chi, kl, f | False)
            else:
                yield from self._generate_rec_kl(chi, kl, True)
            if idx < len(ptr.keys):
                yield ptr.keys[idx]
        if not ptr.children:
            for key in ptr.keys[idxl:]:
                yield key

    def _add_rec(self, ptr, key):
        if not ptr.children:
            insort(ptr.keys, key)
        else:
            i = bisect_right(ptr.keys, key)
            p = self._add_rec(ptr.children[i], key)
            if p is not None:
                ptr.keys.insert(i, p.keys.pop())
                ptr.children.insert(i, p)
        return ptr.split()

    def _remove_rec(self, ptr, key):
        idx = bisect_left(ptr.keys, key)
        if idx != len(ptr.keys) and ptr.keys[idx] == key:
            if not ptr.children:
                del ptr.keys[idx]
            else:
                ptr.keys[idx] = self._remove_smallest(ptr.children[idx + 1])
                self._check_underflow(ptr, idx + 1)
            return True
        elif ptr.children and self._remove_rec(ptr.children[idx], key):
            self._check_underflow(ptr, idx)
            return True
        return False

    def _remove_smallest(self, ptr):
        if not ptr.children:
            res = ptr.keys[0]
            del ptr.keys[0]
            return res
        res = self._remove_smallest(ptr.children[0])
        self._check_underflow(ptr, 0)
        return res

    def _check_underflow(self, ptr, idx):
        if len(ptr.children[idx].keys) >= self.B_SIZE - 1:
            return
        elif idx == 0:
            if len(ptr.children[idx + 1].keys) > self.B_SIZE: ptr.shift_rl(idx)
            else: ptr.merge(idx)
        else:
            if len(ptr.children[idx - 1].keys) > self.B_SIZE: ptr.shift_lr(idx - 1)
            else: ptr.merge(idx - 1)

    def add(self, key):
        if key in self:
            return True
        ptr = self.root
        p = self._add_rec(ptr, key)
        if p is not None:
            root = BTreeNode(self.B_SIZE)
            root.keys = [p.keys.pop()]
            root.children = [p, self.root]
            self.root = root
        self.size += 1
        return True

    def remove(self, key):
        flag = self._remove_rec(self.root, key)
        if len(self.root.children) == 1:
            self.root = self.root.children[0]
        if flag: self.size -= 1
        return flag

    def iterate(self, kl):
        return self._generate_rec_kl(self.root, kl, False)

    def prev_key(self, key):
        ptr = self.root
        res = None
        while True:
            idx = bisect_left(ptr.keys, key)
            if idx - 1 >= 0:
                res = ptr.keys[idx - 1]
            if not ptr.children:
                break
            ptr = ptr.children[idx]
        return res

class SortedInterval:
    def __init__(self):
        self.sset = SortedSetBTree()
        self.rs = {}
        self.length = 0

    def add(self, l, r):
        prev_l = self.sset.prev_key(l)
        if prev_l is not None and l <= self.rs[prev_l]:
            l = prev_l
            r = max(r, self.rs[prev_l])
            del self.rs[prev_l]
            self.sset.remove(prev_l)
        removed = []
        for next_l in self.sset.iterate(l):
            if next_l > r:
                break
            removed.append(next_l)
        for next_l in removed:
            r = max(r, self.rs[next_l])
            del self.rs[next_l]
            self.sset.remove(next_l)
        self.sset.add(l)
        self.rs[l] = r
        # 新しく生成された区間の大きさを返す
        return r - l

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


n, q = map(int, input().split())
intervals = [list(map(int, input().split())) for i in range(q)]


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