結果

問題 No.1435 Mmm......
コンテスト
ユーザー ああ
提出日時 2026-05-29 22:30:31
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 446 ms / 2,000 ms
コード長 790 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 264 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 125,904 KB
最終ジャッジ日時 2026-05-29 22:30:47
合計ジャッジ時間 10,692 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def xx(q,w):
    a,b=q
    b=min(w[0],b)
    if a>b:
        a,b=b,a
    b=min(w[1],b)
    return (a,b)

def aa(seg,xx,m):
    while m>1:
        m//=2
        seg[m]=xx(seg[m*2],seg[m*2+1])
def bb(seg,xx,l,r,res):
    while l<r:
        if l&1:
            res=xx(res,seg[l]);l+=1
        if r&1:
            r-=1;res=xx(res,seg[r])
        l//=2;r//=2
    return res

n=int(input())
a=list(map(int,input().split()));v=1<<n.bit_length()
seg1=[0]*v*2
seg2=[(1<<60,1<<60)]*v*2
for i in range(n):
    seg1[i+v]=a[i];aa(seg1,max,i+v)
    seg2[i+v]=(a[i],1<<60);aa(seg2,xx,i+v)
q=0;ans=0
for i in range(n-1):
    q=max(q,i+1)
    while q<n:
        if sum(bb(seg2,xx,i+v,q+1+v,(1<<60,1<<60)))>=bb(seg1,max,i+v,q+1+v,0):
            q+=1
        else:
            break
    ans+=q-i-1
print(ans)
0