結果

問題 No.1435 Mmm......
ユーザー persimmon-persimmon
提出日時 2021-06-09 09:24:26
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 823 bytes
コンパイル時間 1,113 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 105,728 KB
最終ジャッジ日時 2024-11-27 19:26:10
合計ジャッジ時間 4,523 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

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={}
  M,m1,m2=-1,-1,-1
  for i in range(n-1):
    if 0<i and a[i-1] not in tmp:
      ans+=(l-i)
      continue
    l,r=l,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)
    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)
0