結果

問題 No.1435 Mmm......
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-06-08 16:57:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,796 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 117,012 KB
最終ジャッジ日時 2024-05-05 02:50:40
合計ジャッジ時間 4,753 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
57,600 KB
testcase_01 AC 41 ms
52,096 KB
testcase_02 AC 40 ms
52,096 KB
testcase_03 AC 41 ms
52,736 KB
testcase_04 AC 40 ms
52,736 KB
testcase_05 AC 40 ms
52,096 KB
testcase_06 TLE -
testcase_07 -- -
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 # 

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