結果

問題 No.1435 Mmm......
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-06-09 09:16:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,190 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 108,988 KB
最終ジャッジ日時 2024-05-05 19:00:41
合計ジャッジ時間 4,648 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
63,736 KB
testcase_01 AC 43 ms
55,040 KB
testcase_02 AC 42 ms
55,296 KB
testcase_03 AC 44 ms
55,168 KB
testcase_04 AC 47 ms
54,656 KB
testcase_05 AC 43 ms
54,656 KB
testcase_06 TLE -
testcase_07 TLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree():
  def __init__(self,size,f=lambda x,y:x+y,default=0):
    self.size=pow(2,(size-1).bit_length())
    self.f=f
    self.default=default
    self.data=[default]*(self.size*2)
  def update(self,i,x):
    i+=self.size
    self.data[i]=x
    while i:
      i>>=1
      self.data[i]=self.f(self.data[i*2],self.data[i*2+1])
  # 区間[l,r)へのクエリ
  def query(self,l,r):
    l,r=l+self.size,r+self.size
    lret,rret=self.default,self.default
    while l<r:
      if l&1:
        lret=self.f(self.data[l],lret)
        l+=1
      if r&1:
        r-=1
        rret=self.f(self.data[r],rret)
      l>>=1
      r>>=1
    return self.f(lret,rret)
  def get(self,i):
    return self.data[self.size+i]
  def add(self,i,x):
    self.update(i,self.get(i)+x)
def main0(n,a):
  inf=10**10
  def f(x,y):
    ary=[]
    xidx,yidx=0,0
    while len(ary)<2:
      if x[xidx]<y[yidx]:
        ary.append(x[xidx])
        xidx+=1
      else:
        ary.append(y[yidx])
        yidx+=1
    ary.append(max(x[-1],y[-1]))
    return ary
  st=SegmentTree(n,f,default=[inf,inf,0])
  for i,x in enumerate(a):
    st.update(i,[x,inf,x])
  ans=0
  for i in range(n-1):
    l,r=i+1,n
    while r-l>1:
      x=(l+r)//2
      m1,m2,M=st.query(i,x+1)
      if M<=m1+m2:
        l,r=x,r
      else:
        l,r=l,x
    ans+=(l-i)
  return ans
class SegmentTree():
  def __init__(self,size,f=lambda x,y:x+y,default=0):
    self.size=pow(2,(size-1).bit_length())
    self.f=f
    self.default=default
    self.data=[default]*(self.size*2)
  def update(self,i,x):
    i+=self.size
    self.data[i]=x
    while i:
      i>>=1
      self.data[i]=self.f(self.data[i*2],self.data[i*2+1])
  # 区間[l,r)へのクエリ
  def query(self,l,r):
    l,r=l+self.size,r+self.size
    lret,rret=self.default,self.default
    while l<r:
      if l&1:
        lret=self.f(self.data[l],lret)
        l+=1
      if r&1:
        r-=1
        rret=self.f(self.data[r],rret)
      l>>=1
      r>>=1
    return self.f(lret,rret)
  def get(self,i):
    return self.data[self.size+i]
  def add(self,i,x):
    self.update(i,self.get(i)+x)
def main1(n,a):
  inf=10**10
  def f(x,y):
    ary=[]
    xidx,yidx=0,0
    while len(ary)<2:
      if x[xidx]<y[yidx]:
        ary.append(x[xidx])
        xidx+=1
      else:
        ary.append(y[yidx])
        yidx+=1
    ary.append(max(x[-1],y[-1]))
    return ary
  st=SegmentTree(n,f,default=[inf,inf,0])
  for i,x in enumerate(a):
    st.update(i,[x,inf,x])
  ans=0
  l=0
  tmp={}
  for i in range(n-1):
    if 0<i and a[i-1] not in tmp:
      ans+=(l-i)
      continue
    l,r=l,n
    M,m1,m2=-1,-1,-1
    while r-l>1:
      x=(l+r)//2
      m1,m2,M=st.query(i,x+1)
      if M<=m1+m2:
        l,r=x,r
      else:
        l,r=l,x
    ans+=(l-i)
    tmp={M,m1,m2}
  return ans
"""

"""
if __name__=='__main__':
  n=int(input())
  a=list(map(int,input().split()))
  #ret0=main0(n,a)
  ret1=main1(n,a)
  #print(ret0)
  print(ret1)

from random import randint
if __name__=='__main__1':
  for _ in range(100):
    n=randint(2,30)
    a=[randint(1,30) for _ in range(n)]
    ret0=main0(n,a)
    ret1=main1(n,a)
    if ret0!=ret1:
      print(n)
      print(*a)
      print(ret0,ret1)
0