結果

問題 No.674 n連勤
ユーザー convexineq
提出日時 2023-05-09 12:28:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 307 ms / 2,000 ms
コード長 3,752 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 100,608 KB
最終ジャッジ日時 2024-11-25 23:44:55
合計ジャッジ時間 3,469 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class BIT: #0-indexed
def __init__(self, n):
self.size = n
self.tree = [0]*(n+1)
self.depth = n.bit_length()
self.n0 = 1<<self.depth
# self.element = [0]*(n+1)
def get_sum(self, i): #a_0 + ... + a_{i} #
s = 0; i += 1
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def query(self,l,r): #a_l + ... + a_r
return self.get_sum(r) - self.get_sum(l-1)
def add(self, i, x):
i += 1
while i <= self.size:
self.tree[i] += x
i += i & -i
# self.element[i] += x
#def get(self,i): return element[i]
def bisect_left(self,w):
# w index
#w self.size
if w <= 0: return 0
x,k = 0,self.n0
for _ in range(self.depth):
k >>= 1
if x+k <= self.size and self.tree[x+k] < w:
w -= self.tree[x+k]
x += k
return x
class interval_manager: #0-indexed
def __init__(self, n, A=None):
self.n = n
self.isL = BIT(n)
INIT_DATA() #
if A is not None:
assert len(A) == n
self.val = A[::]
self.nxt = list(range(1,n+1))
self.prv = list(range(-1,n))
for i in range(1,n+1): # isL[i] = 1
self.isL.tree[i] = i&-i
else: # 0
self.val = [0]*n
self.nxt = [0]*n
self.nxt[0] = n
self.prv = [-1]*(n+1)
self.prv[-1] = 0
self.isL.add(0,1)
def left(self,i): # i
return self.isL.bisect_left(self.isL.get_sum(i))
def right(self,i): # i
return self.nxt[self.left(i)]
def get(self,i): # A[i]
return self.val[self.left(i)]
def _cut(self,L,i): # [L,nxt[L]) i .
R = self.nxt[L]
self.prv[R] = self.nxt[L] = i
self.prv[i] = L
self.nxt[i] = R
self.val[i] = self.val[L]
self.isL.add(i,1)
def debug(self):
print("sa ",sa)
print("isL",[self.isL.query(i,i) for i in range(self.n)])
print("val",self.val)
print("nxt",self.nxt)
print("prv",self.prv)
def update(self,L,R,x):
# cut
LL = self.left(L)
if L != LL:
self._cut(LL,L)
RL = self.left(R-1)
if R != self.nxt[RL]:
self._cut(RL,R)
### connect
if L and self.val[self.prv[L]] == x:
L = self.prv[L]
if R != self.n and self.val[R] == x:
R = self.nxt[R]
### delete and add
LL = L
while True:
nxt = self.nxt[L]
DELETE(L,nxt,self.val[L])
L = nxt
if L == R: break
self.isL.add(L,-1)
ADD(LL,R,x)
self.nxt[LL] = R
self.prv[R] = LL
self.val[LL] = x
#####################################
import sys
readline = sys.stdin.readline
D,Q = map(int,readline().split())
def INIT_DATA():
return
def DELETE(L,R,x):
return
def ADD(L,R,x):
global ans
ans = max(ans,x*(sa[R]-sa[L]))
a = [0]*Q
b = [0]*Q
for i in range(Q):
a[i],b[i] = map(int,readline().split())
b[i] += 1
INF = 1<<60
sa = sorted(set([0]+a+b+[INF]))
za = {v:i for i,v in enumerate(sa)}
data = interval_manager(len(sa))
ans = 0
for l,r in zip(a,b):
il = za[l]
ir = za[r]
data.update(il,ir,1)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0