結果
問題 | No.674 n連勤 |
ユーザー |
|
提出日時 | 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 |
ソースコード
class Bit:def __init__(self, n):""":param n: number of elements"""self.n = nself.tree = [0]*(n+1)self.depth = n.bit_length() - 1def sum(self, i):""" return summation of elements in [0,i) """s = 0i -= 1while i >= 0:s += self.tree[i]i = (i & (i + 1) )- 1return sdef 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] += xi |= i + 1def 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_ = 0pos = -1 # 1-indexed の時は pos = 0if 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.nsum_ += self.tree[k]pos += 1 << iif 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.nsum_ += self.tree[k]pos += 1 << ireturn pos, sum_def __getitem__(self, i):""" [a0, a1, a2, ...] """if i<0: i=self.n+ireturn 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 = 0self.code = {}self.decode = []for i, b in enumerate(self.data):self.code[b] = iself.decode.append(b)for a in A:self.add(a)def add(self,x):self.p.add(self.code[x], 1)self.size += 1def remove(self,x):self.p.add(self.code[x], -1)self.size -= 1def order(self,x):"""return x rank in order of decreasing(1-indexed)BIT.order(x) = bisect_left(BIT.sort(),x) + 1BIT.minimum(BIT.order(x)) = BIT.lower_bound(x)"""if x in self.code.keys():return self.p.sum(self.code[x]) + 1else:return self.p.sum(bisect_right(self.data, x)) + 1def 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 += 1if 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] + equalelse: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 - equalelse:y = bisect_left(self.data, x-1)k = self.p.sum(y) + 1if 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.sizedef __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 = 0def 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_lr = 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 - ldef sum(self):res=0for l in self.SL:res+=self.rs[l]-l+1return resdef __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 inputexample = iter("""30 1210 1015 1510 1114 1514 169 1112 1413 1719 2913 1811 290 13""".strip().split("\n"))input = lambda: next(example)#########################################################import sysinput = sys.stdin.readlinefrom 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 = 0for l, r in intervals:ans = max(SI.add(l, r + 1), ans)print(ans)