結果

問題 No.1435 Mmm......
コンテスト
ユーザー persimmon-persimmon
提出日時 2021-06-08 16:57:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,796 bytes
コンパイル時間 318 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 174,336 KB
最終ジャッジ日時 2024-11-26 19:54:51
合計ジャッジ時間 67,782 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 TLE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

n=int(input())
a=list(map(int,input().split()))
"""
aiの大きいものから順に考える？
二分探索
Mを固定?
aiの小さい順にやってく？
端を固定する方がいい？
r=l+1のときは必ず満たす。rを離していくと、どこかの時点で条件満たさなくなる。二分探索っぽい
最大最小はセグメントツリーでOK
2番目は？セグメントツリーでいける？
[[a0,inf],[a1,inf],[a2,inf],..,]
いけそう

"""

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)
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
  return ary
st_min=SegmentTree(n,f,default=[inf,inf])
st_max=SegmentTree(n,max,default=0)
for i,x in enumerate(a):
  st_min.update(i,[x,inf])
  st_max.update(i,x)
ans=0
for i in range(n-1):
  l,r=i+1,n
  while r-l>1:
    x=(l+r)//2
    m1,m2=st_min.query(i,x+1)
    M=st_max.query(i,x+1)
    if M<=m1+m2:
      l,r=x,r
    else:
      l,r=l,x
  ans+=(l-i)
print(ans)
0