結果

問題 No.674 n連勤
ユーザー neterukunneterukun
提出日時 2021-06-08 22:19:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 854 ms / 2,000 ms
コード長 6,317 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 92,724 KB
最終ジャッジ日時 2024-05-05 09:39:51
合計ジャッジ時間 5,488 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
53,504 KB
testcase_01 AC 41 ms
53,504 KB
testcase_02 AC 42 ms
53,760 KB
testcase_03 AC 41 ms
54,144 KB
testcase_04 AC 42 ms
53,504 KB
testcase_05 AC 42 ms
53,632 KB
testcase_06 AC 41 ms
53,632 KB
testcase_07 AC 42 ms
53,888 KB
testcase_08 AC 43 ms
53,248 KB
testcase_09 AC 42 ms
53,888 KB
testcase_10 AC 42 ms
53,888 KB
testcase_11 AC 119 ms
77,356 KB
testcase_12 AC 283 ms
79,976 KB
testcase_13 AC 155 ms
80,384 KB
testcase_14 AC 140 ms
80,128 KB
testcase_15 AC 174 ms
80,640 KB
testcase_16 AC 854 ms
92,724 KB
testcase_17 AC 625 ms
90,616 KB
testcase_18 AC 789 ms
88,320 KB
testcase_19 AC 141 ms
80,128 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from array import array


def xorshift32():
    y = 2463534242
    def inner():
        nonlocal y
        y = y ^ (y << 13 & 0xFFFFFFFF)
        y = y ^ (y >> 17 & 0xFFFFFFFF)
        y = y ^ (y << 5 & 0xFFFFFFFF)
        return y & 0xFFFFFFFF
    return inner


class SortedSetTreap:
    def __init__(self):
        self.root = -1
        self.pow_sz = 1
        self.rand32 = xorshift32()
        self.stack = array("i", [0])
        self.l = array("i", [-1])
        self.r = array("i", [-1])
        self.p = array("i", [-1])
        self.pris = array("I", [self.rand32()])
        self.keys = [0]

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

    def __len__(self):
        return self.pow_sz - len(self.stack)

    def __iter__(self):
        def dfs(nd):
            if self.l[nd] != -1:
                yield from dfs(self.l[nd])
            yield self.keys[nd]
            if self.r[nd] != -1:
                yield from dfs(self.r[nd])
        if self.root != -1:
            yield from dfs(self.root)

    def _new_node(self, key):
        if self.stack:
            nd = self.stack.pop()
            self.keys[nd] = key
            return nd
        else:
            self.stack = array("i", [nd for nd in range(self.pow_sz, self.pow_sz << 1)])
            self.l += array("i", [-1] * self.pow_sz)
            self.r += array("i", [-1] * self.pow_sz)
            self.p += array("i", [-1] * self.pow_sz)
            self.pris += array("I", [self.rand32() for _ in range(self.pow_sz)])
            self.keys += [0] * self.pow_sz
            self.pow_sz <<= 1
            return self._new_node(key)

    def _search(self, key):
        nd = self.root
        while nd != -1:
            if key < self.keys[nd]: nd = self.l[nd]
            elif key > self.keys[nd]: nd = self.r[nd]
            else: return True
        return False

    def add(self, key):
        if self.root == -1:
            self.root = self._new_node(key)
            return True

        nd = self.root
        while True:
            if key < self.keys[nd]:
                if self.l[nd] == -1:
                    self.l[nd] = self._new_node(key)
                    self.p[self.l[nd]] = nd
                    nd = self.l[nd]
                    break
                nd = self.l[nd]
            elif key > self.keys[nd]:
                if self.r[nd] == -1:
                    self.r[nd] = self._new_node(key)
                    self.p[self.r[nd]] = nd
                    nd = self.r[nd]
                    break
                nd = self.r[nd]
            else:
                return False

        while self.p[nd] != -1 and self.pris[self.p[nd]] > self.pris[nd]:
            if self.r[self.p[nd]] == nd: self._rotl(self.p[nd])
            else: self._rotr(self.p[nd])
        return True

    def _rotl(self, nd):
        pv = self.r[nd]
        self.p[pv] = self.p[nd]
        if self.p[pv] != -1:
            if self.l[self.p[pv]] == nd: self.l[self.p[pv]] = pv
            else: self.r[self.p[pv]] = pv
        self.r[nd] = self.l[pv]
        if self.r[nd] != -1: self.p[self.r[nd]] = nd
        self.p[nd] = pv
        self.l[pv] = nd
        if nd == self.root: self.root = pv

    def _rotr(self, nd):
        pv = self.l[nd]
        self.p[pv] = self.p[nd]
        if self.p[pv] != -1:
            if self.r[self.p[pv]] == nd: self.r[self.p[pv]] = pv
            else: self.l[self.p[pv]] = pv
        self.l[nd] = self.r[pv]
        if self.l[nd] != -1: self.p[self.l[nd]] = nd
        self.p[nd] = pv
        self.r[pv] = nd
        if nd == self.root: self.root = pv

    def remove(self, key):
        if self.root == -1: return False

        nd = self.root
        while True:
            if nd == -1: return False
            elif key < self.keys[nd]: nd = self.l[nd]
            elif key > self.keys[nd]: nd = self.r[nd]
            else: break

        while self.l[nd] != -1 or self.r[nd] != -1:
            if self.l[nd] == -1: self._rotl(nd)
            elif self.r[nd] == -1: self._rotr(nd)
            elif self.pris[self.l[nd]] < self.pris[self.r[nd]]: self._rotr(nd)
            else: self._rotl(nd)

        if nd == self.root: self.root = -1
        elif self.l[self.p[nd]] == nd: self.l[self.p[nd]] = -1
        else: self.r[self.p[nd]] = -1
        self.stack.append(nd)
        return True

    def iterate(self, lower):
        def dfs(nd):
            if self.l[nd] != -1 and (self.keys[nd] > lower):
                yield from dfs(self.l[nd])
            if self.keys[nd] >= lower:
                yield self.keys[nd]
            if self.r[nd] != -1:
                yield from dfs(self.r[nd])
        if self.root != -1:
            yield from dfs(self.root)

    def next_val(self, lower):
        ret = None
        nd = self.root
        while nd != -1:
            if self.keys[nd] >= lower:
                ret = self.keys[nd]
                nd = self.l[nd]
            else: nd = self.r[nd]
        return ret

    def prev_val(self, upper):
        ret = None
        nd = self.root
        while nd != -1:
            if self.keys[nd] < upper:
                ret = self.keys[nd]
                nd = self.r[nd]
            else: nd = self.l[nd]
        return ret


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

    def add(self, l, r):
        prev_l = self.sset.prev_val(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