結果

問題 No.1435 Mmm......
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-06-09 11:03:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,068 ms / 2,000 ms
コード長 4,308 bytes
コンパイル時間 350 ms
コンパイル使用メモリ 87,104 KB
実行使用メモリ 134,616 KB
最終ジャッジ日時 2023-08-18 15:33:30
合計ジャッジ時間 21,946 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
71,164 KB
testcase_01 AC 71 ms
71,440 KB
testcase_02 AC 72 ms
71,180 KB
testcase_03 AC 72 ms
71,256 KB
testcase_04 AC 71 ms
71,328 KB
testcase_05 AC 71 ms
71,300 KB
testcase_06 AC 714 ms
110,500 KB
testcase_07 AC 800 ms
116,156 KB
testcase_08 AC 863 ms
120,676 KB
testcase_09 AC 788 ms
117,944 KB
testcase_10 AC 751 ms
113,800 KB
testcase_11 AC 717 ms
112,968 KB
testcase_12 AC 671 ms
111,944 KB
testcase_13 AC 658 ms
109,732 KB
testcase_14 AC 543 ms
102,188 KB
testcase_15 AC 802 ms
121,752 KB
testcase_16 AC 762 ms
114,740 KB
testcase_17 AC 630 ms
105,144 KB
testcase_18 AC 901 ms
122,108 KB
testcase_19 AC 735 ms
112,596 KB
testcase_20 AC 826 ms
119,092 KB
testcase_21 AC 1,025 ms
130,608 KB
testcase_22 AC 1,068 ms
121,552 KB
testcase_23 AC 922 ms
134,616 KB
testcase_24 AC 900 ms
133,476 KB
testcase_25 AC 963 ms
134,280 KB
testcase_26 AC 947 ms
134,096 KB
testcase_27 AC 957 ms
134,524 KB
権限があれば一括ダウンロードができます

ソースコード

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):
  if n==2:return 1
  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
  r=1
  tmp={}
  for i in range(n-1):
    #if 0<i and a[i-1] not in tmp:
    #  ans+=(r-i)
    #  continue
    
    if i==0:
      _l,_r=r,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
      r=_l
      tmp={M,m1,m2}
    else:
      r=max(r,i+1)
      m1,m2,M=st.query(i,r+1) # これは必ず条件を満たす。
      for j in range(r+1,n):
        m=a[j]
        if m2==inf and 1:
          ary=[m1,M,m]
          ary.sort()
          if ary[-1]<=ary[0]+ary[1]:
            r=j
            m1,m2,M=ary
            continue
          else:
            break
        if m2<=m<=M:
          r=j
        elif M<m:
          if m<=m1+m2:
            r=j
            M=m
          else:
            break
        elif m1<=m<m2:
          if M<=m1+m:
            r=j
            m2=m
          else:
            break
        elif m<m1:
          if M<=m+m1:
            r=j
            m1,m2=m,m1
          else:
            break
        else:
          pass
          #break
      tmp={M,m1,m2}
    ans+=(r-i)
    #print(i,r,ans,tmp,st.query(i,r+1))
    assert r>i,f"error{r,i}"
  #print(st.query(0,1))
  #print(st.query(0,2))
  #print(st.query(0,3))
  return ans

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

  exit()
  ret0=main0(n,a)
  print(ret0)

from random import randint
from datetime import datetime
if __name__=='__main__':
  t=datetime.now().timestamp()
  for _ in range(1):
    n=randint(10**4,10**4)
    n=10**5
    a=[randint(1,10) for _ in range(n)]
    #ret0=main0(n,a)
    ret1=main1(n,a)
    #if ret0!=ret1:
    #  print(n)
    #  print(*a)
    #  print(ret0,ret1)
    #  break
  print(datetime.now().timestamp()-t)
0