結果
| 問題 | No.2930 Larger Mex |
| ユーザー |
 vwxyz
|
| 提出日時 | 2024-10-12 15:23:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 292 ms / 2,000 ms |
| コード長 | 25,709 bytes |
| コンパイル時間 | 177 ms |
| コンパイル使用メモリ | 82,396 KB |
| 実行使用メモリ | 127,360 KB |
| 最終ジャッジ日時 | 2024-10-12 15:24:09 |
| 合計ジャッジ時間 | 14,597 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 49 ms
60,420 KB |
| testcase_01 | AC | 48 ms
61,844 KB |
| testcase_02 | AC | 48 ms
61,044 KB |
| testcase_03 | AC | 101 ms
77,252 KB |
| testcase_04 | AC | 85 ms
76,804 KB |
| testcase_05 | AC | 89 ms
77,220 KB |
| testcase_06 | AC | 92 ms
77,244 KB |
| testcase_07 | AC | 89 ms
76,916 KB |
| testcase_08 | AC | 239 ms
102,288 KB |
| testcase_09 | AC | 205 ms
100,348 KB |
| testcase_10 | AC | 220 ms
103,696 KB |
| testcase_11 | AC | 189 ms
97,816 KB |
| testcase_12 | AC | 247 ms
116,564 KB |
| testcase_13 | AC | 223 ms
108,020 KB |
| testcase_14 | AC | 259 ms
125,600 KB |
| testcase_15 | AC | 226 ms
119,536 KB |
| testcase_16 | AC | 237 ms
117,216 KB |
| testcase_17 | AC | 257 ms
124,184 KB |
| testcase_18 | AC | 240 ms
118,856 KB |
| testcase_19 | AC | 274 ms
124,804 KB |
| testcase_20 | AC | 292 ms
125,804 KB |
| testcase_21 | AC | 288 ms
124,692 KB |
| testcase_22 | AC | 256 ms
125,312 KB |
| testcase_23 | AC | 270 ms
118,456 KB |
| testcase_24 | AC | 251 ms
121,784 KB |
| testcase_25 | AC | 260 ms
125,088 KB |
| testcase_26 | AC | 197 ms
112,152 KB |
| testcase_27 | AC | 177 ms
101,968 KB |
| testcase_28 | AC | 194 ms
108,940 KB |
| testcase_29 | AC | 188 ms
104,804 KB |
| testcase_30 | AC | 215 ms
121,032 KB |
| testcase_31 | AC | 181 ms
113,776 KB |
| testcase_32 | AC | 207 ms
121,412 KB |
| testcase_33 | AC | 205 ms
122,956 KB |
| testcase_34 | AC | 272 ms
115,556 KB |
| testcase_35 | AC | 191 ms
97,668 KB |
| testcase_36 | AC | 266 ms
114,288 KB |
| testcase_37 | AC | 258 ms
110,500 KB |
| testcase_38 | AC | 245 ms
115,288 KB |
| testcase_39 | AC | 242 ms
116,036 KB |
| testcase_40 | AC | 241 ms
115,356 KB |
| testcase_41 | AC | 247 ms
104,304 KB |
| testcase_42 | AC | 200 ms
102,844 KB |
| testcase_43 | AC | 187 ms
100,716 KB |
| testcase_44 | AC | 199 ms
105,492 KB |
| testcase_45 | AC | 221 ms
105,208 KB |
| testcase_46 | AC | 208 ms
125,496 KB |
| testcase_47 | AC | 202 ms
125,080 KB |
| testcase_48 | AC | 176 ms
113,652 KB |
| testcase_49 | AC | 207 ms
126,908 KB |
| testcase_50 | AC | 190 ms
103,044 KB |
| testcase_51 | AC | 273 ms
127,360 KB |
| testcase_52 | AC | 279 ms
126,836 KB |
ソースコード
from collections import defaultdict
class Segment_Tree:
def __init__(self,N,f,e,lst=None,dynamic=False,bisect_search=True):
self.f=f
self.e=e
self.N=N
self.bisect_search=bisect_search
if self.bisect_search:
self.le=1
while self.le<self.N:
self.le*=2
else:
self.le=self.N
if dynamic:
self.segment_tree=defaultdict(lambda:self.e)
else:
if lst==None:
self.segment_tree=[self.e]*2*self.le
else:
assert len(lst)<=self.N
self.segment_tree=[self.e]*self.le+[x for x in lst]+[self.e]*(self.le-len(lst))
for i in range(self.le-1,0,-1):
self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
def __getitem__(self,i):
if type(i)==int:
if -self.le<=i<0:
return self.segment_tree[i+self.le*2]
elif 0<=i<self.le:
return self.segment_tree[i+self.le]
else:
raise IndexError("list index out of range")
else:
a,b,c=i.start,i.stop,i.step
if a==None:
a=self.le
else:
a+=self.le
if b==None:
b=self.le*2
else:
b+=self.le
return self.segment_tree[slice(a,b,c)]
def __setitem__(self,i,x):
if -self.le<=i<0:
i+=self.le*2
elif 0<=i<self.le:
i+=self.le
else:
raise IndexError("list index out of range")
self.segment_tree[i]=x
while i>1:
i>>= 1
self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
def Build(self,lst):
for i,x in enumerate(lst,self.le):
self.segment_tree[i]=x
for i in range(self.le-1,0,-1):
self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
def Fold(self,L=None,R=None):
if L==None:
L=self.le
else:
assert 0<=L<=self.N
L+=self.le
if R==None:
R=self.le*2
else:
assert 0<=R<=self.N
R+=self.le
vL=self.e
vR=self.e
while L<R:
if L&1:
vL=self.f(vL,self.segment_tree[L])
L+=1
if R&1:
R-=1
vR=self.f(self.segment_tree[R],vR)
L>>=1
R>>=1
return self.f(vL,vR)
def Fold_Index(self,L=None,R=None):
if L==None:
L=self.le
else:
assert 0<=L<=self.N
L+=self.le
if R==None:
R=self.le*2
else:
assert 0<=R<=self.N
R+=self.le
if L==R:
return None
x=self.Fold(L-self.le,R-self.le)
while L<R:
if L&1:
if self.segment_tree[L]==x:
i=L
break
L+=1
if R&1:
R-=1
if self.segment_tree[R]==x:
i=R
break
L>>=1
R>>=1
while i<self.le:
if self.segment_tree[i]==self.segment_tree[i<<1]:
i<<=1
else:
i<<=1
i|=1
i-=self.le
return i
def Bisect_Right(self,L=None,f=None):
assert self.bisect_search
if L==self.le:
return self.le
if L==None:
L=0
assert 0<=L<=self.N
L+=self.le
vl=self.e
vr=self.e
l,r=L,self.le*2
while l<r:
if l&1:
vl=self.f(vl,self.segment_tree[l])
l+=1
if r&1:
r-=1
vr=self.f(self.segment_tree[r],vr)
l>>=1
r>>=1
if f(self.f(vl,vr)):
return self.N
v=self.e
while True:
while L%2==0:
L>>=1
vv=self.f(v,self.segment_tree[L])
if f(vv):
v=vv
L+=1
else:
while L<self.le:
L<<=1
vv=self.f(v,self.segment_tree[L])
if f(vv):
v=vv
L+=1
return L-self.le
def Bisect_Left(self,R=None,f=None):
assert self.bisect_search
if R==0:
return 0
if R==None:
R=self.le
assert 0<=R<=self.N
R+=self.le
vl=self.e
vr=self.e
l,r=self.le,R
while l<r:
if l&1:
vl=self.f(vl,self.segment_tree[l])
l+=1
if r&1:
r-=1
vr=self.f(self.segment_tree[r],vr)
l>>=1
r>>=1
if f(self.f(vl,vr)):
return 0
v=self.e
while True:
R-=1
while R>1 and R%2:
R>>=1
vv=self.f(self.segment_tree[R],v)
if f(vv):
v=vv
else:
while R<self.le:
R=2*R+1
vv=self.f(self.segment_tree[R],v)
if f(vv):
v=vv
R-=1
return R+1-self.le
def __str__(self):
return "["+", ".join(map(str,[self.segment_tree[i] for i in range(self.le,self.le+self.N)]))+"]"
def __repr__(self):
return "Segment_Tree("+str(self)+")"
class Segment_Tree_2d:
def __init__(self,N,M,f,e,lst=None,dynamic=False):
self.N=N
self.M=M
self.f=f
self.e=e
if dynamic:
self.segment_tree=defaultdict(lambda:defaultdict(lambda:e))
else:
if lst==None:
self.segment_tree=[[self.e]*2*self.M for i in range(2*self.N)]
else:
assert len(lst)<=self.N
assert all(len(lst[i])<=self.M for i in range(self.N))
self.segment_tree=[[self.e]*2*self.M for i in range(self.N)]+[[self.e]*self.M+lst[i]+[self.e]*(self.M-len(lst[i])) for i in range(len(lst))]+[[self.e]*2*self.M for i in range(self.N-len(lst))]
for i in range(self.N-1,0,-1):
for j in range(2*self.M-1,self.M-1,-1):
self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])
for i in range(2*self.N-1,-1,-1):
for j in range(self.M-1,0,-1):
self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])
def __getitem__(self,tpl):
i,j=tpl
i+=self.N
j+=self.M
return self.segment_tree[i][j]
def __setitem__(self,tpl,x):
i,j=tpl
i+=self.N
j+=self.M
self.segment_tree[i][j]=x
idxN=[i]
idxM=[j]
while i>1:
i>>=1
idxN.append(i)
while j>1:
j>>=1
idxM.append(j)
i=idxN[0]
for j in idxM[1:]:
self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])
for i in idxN[1:]:
for j in idxM:
self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])
def Build(self,lst):
assert len(lst)<=self.N
assert all(len(lst[i] for i in range(self.N))<=self.M)
for i in range(len(lst)):
for j in range(len(lst[i])):
self.segment_tree[i+self.N][j+self.M]=lst[i][j]
for i in range(self.N-1,0,-1):
for j in range(2*self.M-1,self.M-1,-1):
self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])
for i in range(2*self.N-1,-1,-1):
for j in range(self.M-1,0,-1):
self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])
def Fold(self,LN=None,RN=None,LM=None,RM=None):
LN+=self.N
RN+=self.N
LM+=self.M
RM+=self.M
idxN=[]
idxM=[]
while LN<RN:
if LN&1:
idxN.append(LN)
LN+=1
if RN&1:
RN-=1
idxN.append(RN)
LN>>=1
RN>>=1
while LM<RM:
if LM&1:
idxM.append(LM)
LM+=1
if RM&1:
RM-=1
idxM.append(RM)
LM>>=1
RM>>=1
retu=self.e
for i in idxN:
for j in idxM:
retu=self.f(retu,self.segment_tree[i][j])
return retu
def Fold_Index(self,LN=None,RN=None,LM=None,RM=None):
if LN==None:
LN=self.N
else:
LN+=self.N
if RN==None:
RN=self.N*2
else:
RN+=self.N
if LM==None:
LM=self.M
else:
LM+=self.M
if RM==None:
RM=self.M*2
else:
RM+=self.M
if LN==RN and LM==RM:
return None
idxN=[]
idxM=[]
while LN<RN:
if LN&1:
idxN.append(LN)
LN+=1
if RN&1:
RN-=1
idxN.append(RN)
LN>>=1
RN>>=1
while LM<RM:
if LM&1:
idxM.append(LM)
LM+=1
if RM&1:
RM-=1
idxM.append(RM)
LM>>=1
RM>>=1
v=self.e
for i in idxN:
for j in idxM:
v=self.f(v,self.segment_tree[i][j])
for i in idxN:
for j in idxM:
if v==self.f(v,self.segment_tree[i][j]):
break
else:
continue
break
while i<self.N:
if self.segment_tree[i<<1][j]==v:
i<<=1
else:
i<<=1
i|=1
while j<self.M:
if self.segment_tree[i][j<<1]==v:
j<<=1
else:
j<<=1
j|=1
return i,j
def __str__(self):
m=max(len(str(self.segment_tree[i][j])) for i in range(self.N,self.N*2) for j in range(self.M,self.M*2))
return "\n".join(["["+", ".join(map(lambda s:" "*(m-len(str(s)))+str(s),self.segment_tree[i][self.M:]))+"]" for i in range(self.N,self.N*2)])
def __repr__(self):
return "Segment_Tree_2d(\n"+str(self)+")"
class Dual_Segment_Tree:
def __init__(self,N,f_act,e_act,operate,lst):
self.N=N
self.f_act=f_act
self.e_act=e_act
self.operate=operate
self.lst=[None]*self.N
for i,x in enumerate(lst):
self.lst[i]=x
self.segment_tree_act=[self.e_act]*(self.N+self.N)
def __getitem__(self,i):
if type(i) is int:
if -self.N<=i<0:
i+=self.N*2
elif 0<=i<self.N:
i+=self.N
else:
raise IndexError("list index out of range")
self.Propagate_Above(i)
return self.Operate_At(i)
else:
a,b,c=i.start,i.stop,i.step
if a==None or a<-self.N:
a=0
elif self.N<=a:
a=self.N
elif a<0:
a+=self.N
if b==None or self.N<=b:
b=self.N
elif b<-self.N:
b=0
elif b<0:
b+=self.N
return self.lst[slice(a,b,c)]
def Operate_At(self,i):
return self.operate(self.lst[i-self.N],self.segment_tree_act[i])
def Propagate_At(self,i):
self.segment_tree_act[i<<1]=self.f_act(self.segment_tree_act[i<<1],self.segment_tree_act[i])
self.segment_tree_act[i<<1|1]=self.f_act(self.segment_tree_act[i<<1|1],self.segment_tree_act[i])
self.segment_tree_act[i]=self.e_act
def Propagate_Above(self,i):
H=i.bit_length()-1
for h in range(H,0,-1):
self.Propagate_At(i>>h)
def Operate_Range(self,a,L=None,R=None):
if L==None:
L=self.N
else:
L+=self.N
if R==None:
R=self.N*2
else:
R+=self.N
L0=L//(L&-L)
R0=R//(R&-R)-1
self.Propagate_Above(L0)
self.Propagate_Above(R0)
while L<R:
if L&1:
self.segment_tree_act[L]=self.f_act(self.segment_tree_act[L],a)
L+=1
if R&1:
R-=1
self.segment_tree_act[R]=self.f_act(self.segment_tree_act[R],a)
L>>=1
R>>=1
def Update(self):
for i in range(1,self.N):
self.Propagate_At(i)
self.segment_tree_act[i]=self.e_act
def __str__(self):
import copy
segment_tree_act=copy.deepcopy(self.segment_tree_act)
for i in range(1,self.N):
segment_tree_act[i<<1]=self.f_act(segment_tree_act[i<<1],segment_tree_act[i])
segment_tree_act[i<<1|1]=self.f_act(segment_tree_act[i<<1|1],segment_tree_act[i])
segment_tree_act[i]=self.e_act
segment_tree_act[i]=self.e_act
return "["+", ".join(map(str,[self.operate(x,a) for x,a in zip(self.lst,segment_tree_act[self.N:])]))+"]"
def __repr__(self):
return "Dual_Segment_Tree("+str(self)+")"
class Lazy_Segment_Tree:
def __init__(self,N,f,e,f_act,e_act,operate,lst=None,bisect_search=True):
self.N=N
self.f=f
self.e=e
self.f_act=f_act
self.e_act=e_act
self.operate=operate
self.bisect_search=bisect_search
if self.bisect_search:
self.le=1
while self.le<self.N:
self.le*=2
else:
self.le=self.N
self.segment_tree=[self.e]*(self.le+self.le)
self.segment_tree_act=[self.e_act]*(self.le+self.le)
if lst!=None:
for i,x in enumerate(lst):
self.segment_tree[i+self.le]=x
for i in range(self.le-1,0,-1):
self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
self.segment_tree_act=[self.e_act]*(self.le+self.le)
def __getitem__(self,i):
if type(i) is int:
if -self.le<=i<0:
i+=self.le*2
elif 0<=i<self.le:
i+=self.le
else:
raise IndexError("list index out of range")
self.Propagate_Above(i)
self.Recalculate_Above(i)
return self.Operate_At(i)
else:
a,b,c=i.start,i.stop,i.step
if a==None or a<-self.le:
a=self.le
elif self.le<=a:
a=self.le*2
elif a<0:
a+=self.le*2
else:
a+=self.le
if b==None or self.le<=b:
b=self.le*2
elif b<-self.le:
b=self.le
elif b<0:
b+=self.le*2
else:
b+=self.le
return self.segment_tree[slice(a,b,c)]
def __setitem__(self,i,x):
if -self.le<=i<0:
i+=self.le*2
elif 0<=i<self.le:
i+=self.le
else:
raise IndexError("list index out of range")
self.Propagate_Above(i)
self.segment_tree[i]=x
self.segment_tree_act[i]=self.e_act
self.Recalculate_Above(i)
def Operate_At(self,i):
return self.operate(self.segment_tree[i],self.segment_tree_act[i])
def Propagate_At(self,i):
self.segment_tree[i]=self.Operate_At(i)
self.segment_tree_act[i<<1]=self.f_act(self.segment_tree_act[i<<1],self.segment_tree_act[i])
self.segment_tree_act[i<<1|1]=self.f_act(self.segment_tree_act[i<<1|1],self.segment_tree_act[i])
self.segment_tree_act[i]=self.e_act
def Propagate_Above(self,i):
H=i.bit_length()-1
for h in range(H,0,-1):
self.Propagate_At(i>>h)
def Recalculate_Above(self,i):
while i>1:
i>>=1
self.segment_tree[i]=self.f(self.Operate_At(i<<1),self.Operate_At(i<<1|1))
def Build(self,lst):
for i,x in enumerate(lst):
self.segment_tree[i+self.le]=x
for i in range(self.le-1,0,-1):
self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
self.segment_tree_act=[self.e_act]*(self.le+self.le)
def Fold(self,L=None,R=None):
if L==None:
L=self.le
else:
assert 0<=L<=self.le
L+=self.le
if R==None:
R=self.le*2
else:
assert 0<=R<=self.le
R+=self.le
self.Propagate_Above(L//(L&-L))
self.Propagate_Above(R//(R&-R)-1)
vL=self.e
vR=self.e
while L<R:
if L&1:
vL=self.f(vL,self.Operate_At(L))
L+=1
if R&1:
R-=1
vR=self.f(self.Operate_At(R),vR)
L>>=1
R>>=1
return self.f(vL,vR)
def Fold_Index(self,L=None,R=None):
if L==None:
L=self.le
else:
assert 0<=L<=self.le
L+=self.le
if R==None:
R=self.le*2
else:
assert 0<=R<=self.le
R+=self.le
if L==R:
return None
x=self.Fold(L-self.le,R-self.le)
while L<R:
if L&1:
if self.segment_tree[L]==x:
i=L
break
L+=1
if R&1:
R-=1
if self.segment_tree[R]==x:
i=R
break
L>>=1
R>>=1
while i<self.le:
if self.segment_tree[i]==self.segment_tree[i<<1]:
i<<=1
else:
i<<=1
i|=1
i-=self.le
return i
def Operate_Range(self,a,L=None,R=None):
if L==None:
L=self.le
else:
assert 0<=L<=self.le
L+=self.le
if R==None:
R=self.le*2
else:
assert 0<=R<=self.le
R+=self.le
L0=L//(L&-L)
R0=R//(R&-R)-1
self.Propagate_Above(L0)
self.Propagate_Above(R0)
while L<R:
if L&1:
self.segment_tree_act[L]=self.f_act(self.segment_tree_act[L],a)
L+=1
if R&1:
R-=1
self.segment_tree_act[R]=self.f_act(self.segment_tree_act[R],a)
L>>=1
R>>=1
self.Recalculate_Above(L0)
self.Recalculate_Above(R0)
def Update(self):
for i in range(1,self.le):
self.Propagate_At(i)
for i in range(self.le,self.le*2):
self.segment_tree[i]=self.Operate_At(i)
self.segment_tree_act[i]=self.e_act
for i in range(self.le-1,0,-1):
self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
def Bisect_Right(self,L=None,f=None):
assert self.bisect_search
if L==self.le:
return self.le
if L==None:
L=0
assert 0<=L<=self.le
L+=self.le
self.Propagate_Above(L//(L&-L))
self.Propagate_Above(self.le//(self.le&-self.le)-1)
l,r=L,self.le*2
vl=self.e
vr=self.e
while l<r:
if l&1:
vl=self.f(vl,self.Operate_At(l))
l+=1
if r&1:
r-=1
vr=self.f(self.Operate_At(r),vr)
l>>=1
r>>=1
if f(self.f(vl,vr)):
return self.N
v=self.e
self.Propagate_Above(L)
while True:
while L%2==0:
L>>=1
vv=self.f(v,self.Operate_At(L))
if f(vv):
v=vv
L+=1
else:
while L<self.le:
self.Propagate_At(L)
L<<=1
vv=self.f(v,self.Operate_At(L))
if f(vv):
v=vv
L+=1
return L-self.le
def Bisect_Left(self,R=None,f=None):
if R==0:
return 0
if R==None:
R=self.le
assert 0<=R<=self.le
R+=self.le
self.Propagate_Above(self.le//(self.le&-self.le))
self.Propagate_Above(R//(R&-R)-1)
vl=self.e
vr=self.e
l,r=self.le,R
while l<r:
if l&1:
vl=self.f(vl,self.Operate_At(l))
l+=1
if r&1:
r-=1
vr=self.f(self.Operate_At(r),vr)
l>>=1
r>>=1
if f(self.f(vl,vr)):
return 0
v=self.e
self.Propagate_Above(R-1)
while True:
R-=1
while R>1 and R%2:
R>>=1
vv=self.f(self.Operate_At(R),v)
if f(vv):
v=vv
else:
while R<self.le:
self.Propagate_At(R)
R=(R<<1)|1
vv=self.f(self.Operate_At(R),v)
if f(vv):
v=vv
R-=1
return R+1-self.le
def __str__(self):
import copy
segment_tree=copy.deepcopy(self.segment_tree)
segment_tree_act=copy.deepcopy(self.segment_tree_act)
for i in range(1,self.le):
segment_tree[i]=self.operate(segment_tree[i],segment_tree_act[i])
segment_tree_act[i<<1]=self.f_act(segment_tree_act[i<<1],segment_tree_act[i])
segment_tree_act[i<<1|1]=self.f_act(segment_tree_act[i<<1|1],segment_tree_act[i])
segment_tree_act[i]=self.e_act
for i in range(self.le,self.le*2):
segment_tree[i]=self.operate(segment_tree[i],segment_tree_act[i])
segment_tree_act[i]=self.e_act
for i in range(self.le-1,0,-1):
segment_tree[i]=self.f(segment_tree[i<<1],segment_tree[i<<1|1])
return "["+", ".join(map(str,[self.operate(x,a) for x,a in zip(segment_tree[self.le:self.le+self.N],segment_tree_act[self.le:])]))+"]"
def __repr__(self):
return "Lazy_Segment_Tree("+str(self)+")"
class Li_Chao_Tree:
def __init__(self,N,X=None,inf=float("inf")):
self.N=N
if X==None:
self.X=[x for x in range(self.N)]
else:
self.X=X
self.idx={x:i for i,x in enumerate(self.X)}
self.inf=inf
self.li_chao_tree=[(0,self.inf)]*(2*self.N)
self.left,self.right=[None]*2*N,[None]*2*N
for i in range(self.N,2*self.N):
self.left[i]=self.X[i-self.N]
self.right[i]=self.X[i-self.N]
for i in range(self.N-1,0,-1):
self.left[i]=self.left[i<<1]
self.right[i]=self.right[i<<1|1]
def add_line_one_segment(self,a,b,i):
queue=[i]
while queue:
i=queue.pop()
aa,bb=self.li_chao_tree[i]
l=a*self.X[self.left[i]]+b
r=a*self.X[self.right[i]]+b
ll=aa*self.X[self.left[i]]+bb
rr=aa*self.X[self.right[i]]+bb
if ll<=l and rr<=r:
continue
if l<=ll and r<=rr:
self.li_chao_tree[i]=(a,b)
continue
queue.append(i<<1)
queue.append(i<<1|1)
def add_line(self,a,b,L=None,R=None):
if L==None:
L=self.N
else:
L+=self.N
if R==None:
R=2*self.N
else:
R+=self.N
while L<R:
if L%2:
self.add_line_one_segment(a,b,L)
L+=1
if R%2:
R-=1
self.add_line_one_segment(a,b,R)
L>>=1
R>>=1
def __call__(self,x):
i=self.idx[x]+self.N
retu=self.inf
while i:
a,b=self.li_chao_tree[i]
retu=min(retu,a*x+b)
i>>=1
return retu
def __getitem__(self,i):
x=self.X[i]
i+=self.N
retu=self.inf
while i:
a,b=self.li_chao_tree[i]
retu=min(retu,a*x+b)
i>>=1
return retu
def __str__(self):
li_chao_tree=[(0,self.inf)]*self.N
for i,x in enumerate(self.X):
ii=i+self.N
while ii:
aa,bb=self.li_chao_tree[ii]
a,b=li_chao_tree[i]
if aa*x+bb<a*x+b:
li_chao_tree[i]=aa,bb
ii>>=1
return "["+", ".join(map(str,li_chao_tree))+"]"
def __repr__(self):
return "Li_Chao_Tree("+str(self)+")"
N,M=map(int,input().split())
A=list(map(int,input().split()))
K=max(A+[M])+1
inf=1<<30
ST=Segment_Tree(K,min,inf,[-1]*K)
def f_act(a,b):
return a+b
def operate(x,a):
return x+a
ans_lst=[0]*(N+2)
for r in range(1,N+1):
a=A[r-1]
ST[a]=r-1
l=ST.Fold(0,M)
if l==inf:
l=r
d0=r-l
d1=r+1
if l>=0:
ans_lst[d0]+=1
ans_lst[d1]-=1
for i in range(1,N+2):
ans_lst[i]+=ans_lst[i-1]
for i in range(1,N+1):
print(ans_lst[i])