結果
| 問題 | No.674 n連勤 |
| コンテスト | |
| ユーザー |
 neterukun
|
| 提出日時 | 2021-06-08 22:19:51 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 802 ms / 2,000 ms |
| コード長 | 6,317 bytes |
| 記録 | |
| コンパイル時間 | 237 ms |
| コンパイル使用メモリ | 81,876 KB |
| 実行使用メモリ | 92,732 KB |
| 最終ジャッジ日時 | 2024-11-27 05:31:43 |
| 合計ジャッジ時間 | 5,363 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
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)