結果
| 問題 | No.674 n連勤 |
| ユーザー |
 None
|
| 提出日時 | 2021-02-17 20:41:36 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 458 ms / 2,000 ms |
| コード長 | 9,413 bytes |
| コンパイル時間 | 330 ms |
| コンパイル使用メモリ | 86,840 KB |
| 実行使用メモリ | 106,048 KB |
| 最終ジャッジ日時 | 2023-10-12 06:49:44 |
| 合計ジャッジ時間 | 5,890 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 75 ms
71,156 KB |
| testcase_01 | AC | 73 ms
71,052 KB |
| testcase_02 | AC | 74 ms
71,220 KB |
| testcase_03 | AC | 74 ms
71,176 KB |
| testcase_04 | AC | 73 ms
71,324 KB |
| testcase_05 | AC | 74 ms
71,316 KB |
| testcase_06 | AC | 74 ms
71,108 KB |
| testcase_07 | AC | 76 ms
71,448 KB |
| testcase_08 | AC | 73 ms
71,284 KB |
| testcase_09 | AC | 73 ms
71,284 KB |
| testcase_10 | AC | 74 ms
71,280 KB |
| testcase_11 | AC | 144 ms
78,404 KB |
| testcase_12 | AC | 189 ms
81,596 KB |
| testcase_13 | AC | 170 ms
82,092 KB |
| testcase_14 | AC | 193 ms
105,932 KB |
| testcase_15 | AC | 229 ms
100,428 KB |
| testcase_16 | AC | 384 ms
106,048 KB |
| testcase_17 | AC | 383 ms
105,960 KB |
| testcase_18 | AC | 458 ms
99,836 KB |
| testcase_19 | AC | 219 ms
105,732 KB |
ソースコード
#####################################################################################################
##### SortedInterval
#####################################################################################################
"""
10^5個の区間まで間に合う
ベンチマーク
No.674 n連勤: https://yukicoder.me/submissions/617927
"""
class Bit:
__slots__ = ["n","tree","depth"]
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 """
__slots__=["data","n","size","flip","code","decode","p"]
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.flip=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
self.flip+=self.size-self.p.sum(self.code[x]+1) # we can remove this if we do not use flip_number
def remove(self,x):
self.p.add(self.code[x],-1)
self.size-=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 count_range(self,l,r):
""" return number of elements in closed set [l,r]"""
return self.bisect_right(r)-self.bisect_left(l)
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)
k=self.p.sum(y)+1
if k<=self.size:
return self.minimum(k)
def nearest(self,x,k):
""" return k-th nearest value to x """
if k>len(self):
sys.stderr.write("nearest: k (= {0}) is larger than the size of this BitSet\n".format(k))
return
def test(d):
r=self.bisect_right(x+d)-1
l=self.bisect_left(x-d)
return r-l+1<=k
ok,ng=0,10**18+1
while abs(ok-ng)>1:
mid=(ok+ng)//2
if test(mid):
ok=mid
else:
ng=mid
d=ok
r=self.bisect_right(x+d)-1
l=self.bisect_left(x-d)
if d==0:
R=self.lower_bound(x,equal=True)
L=self.upper_bound(x,equal=True)
if abs(x-L)==abs(R-x):
if self.count(L)>=k:
return L
else:
return R
elif abs(x-L)<abs(R-x):
return L
else:
return R
elif r-l+1==k:
R=self[r]
L=self[l]
if abs(x-L)<=abs(R-x):
return R
else:
return L
else:
if l<=0:
return self[r+1]
elif r>=len(self)-1:
return self[l-1]
else:
R=self[r+1]
L=self[l-1]
if abs(x-L)==abs(R-x):
if self.count(L)>=k-(r-l+1):
return L
else:
return R
elif abs(x-L)<abs(R-x):
return L
else:
return R
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:
__slots__ = ["SL","rs","length"]
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)