結果
| 問題 | No.674 n連勤 |
| ユーザー |
 neterukun
|
| 提出日時 | 2021-02-14 20:05:53 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,047 ms / 2,000 ms |
| コード長 | 6,620 bytes |
| コンパイル時間 | 210 ms |
| コンパイル使用メモリ | 82,048 KB |
| 実行使用メモリ | 99,044 KB |
| 最終ジャッジ日時 | 2024-07-22 06:46:29 |
| 合計ジャッジ時間 | 4,600 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
import sys
input = sys.stdin.buffer.readline
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
res = []
for l, r in intervals:
ans = max(si.add(l, r + 1), ans)
res.append(ans)
print("\n".join(map(str, res)))