結果

問題 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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0