結果

問題 No.1435 Mmm......
コンテスト
ユーザー ygd.
提出日時 2021-03-20 00:11:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,764 bytes
コンパイル時間 818 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 114,228 KB
最終ジャッジ日時 2024-11-19 03:15:38
合計ジャッジ時間 6,104 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 1 WA * 5 RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
from heapq import heapify, heappop, heappush
N = int(input())
A = list(map(int,input().split()))
All = N*(N-1)//2
cnt = 0 #M > m1+m2となるものを数えて最後引く
left = 0 
right = 3
HQ = []
MHQ = []
heappush(HQ,A[0]);heappush(MHQ,-A[0])
heappush(HQ,A[1]);heappush(MHQ,-A[1])
heappush(HQ,A[2]);heappush(MHQ,-A[2])
As = [A[0],A[1],A[2]]; As.sort()
removed = defaultdict(int)
maxremoved = defaultdict(int)
m0,m1,M = As
for left in range(N-2):
    #print(left)
    while right < N and m0 + m1 >= M:
        heappush(MHQ,-A[right])
        
        if A[right] > M: #最大が更新された
            M = A[right]
            heappush(HQ,A[right])
        elif m0 <= A[right] < m1: #小さいほうから二番目が更新された
            m1 = A[right]
            heappush(HQ,A[right])
        elif A[right] < m0: #最小が更新された
            m1 = m0
            m0 = A[right]
            heappush(HQ,A[right])
        #まだ条件を満たさないので右側を動かす
        right += 1
        #print(m0,m1,M,left,right)
    #一度条件を満たしたらその右は全部OK
    #print(left,right,HQ,N+1-right)
    if M > m0+m1:
        #print("cnt+",left,right,m0,m1,M,N+1-right)
        cnt += N + 1 - right
    if right - left <= 3:
        if right >= N: #右側がすでにはみ出した。
            break
        heappush(MHQ,-A[right])
        #最大が更新された
        if A[right] > M:
            M = A[right]
            heappush(HQ,A[right])
        elif m0 <= A[right] < m1: #小さいほうから二番目が更新された
            m1 = A[right]
            heappush(HQ,A[right])
        elif A[right] < m0: #最小が更新された
            m1 = m0
            m0 = A[right]
            heappush(HQ,A[right])
        else:
            heappush(HQ,A[right])
        right += 1
    #最大きい値の場合取り除く作業
    if A[left] == M: #最大値の場合
        heappop(MHQ)
        while maxremoved[MHQ[0]] == 1:
            maxremoved[MHQ[0]] -= 1
            heappop(MHQ)
        M = -1*MHQ[0]
    else:
        maxremoved[A[left]] += 1
    #print("MHQ",MHQ)
    #最小値の場合取り除く作業 
    #print("LEFT",left,A[left],m0,m1)
    if A[left] > m1:
        removed[A[left]] += 1
    elif m0 < A[left] <= m1: #m1が変わる可能性がある
        if removed[A[left]] == 0: #一個しかないので変わる
            heappop(HQ) #m0が取り除かれる（そのまま）
            heappop(HQ) #m1が取り除かれる
            while removed[HQ[0]] == 1:
                removed[HQ[0]] -=1
                heappop(HQ)
            m1 = HQ[0] #新しいm1
            heappush(HQ,m0) #m0を戻す
        else: #ストックがあった場合には一つ減る
            removed[A[left]] -= 1
    elif m0 <= A[left]: #m0が変わる可能性がある
        if removed[A[left]] == 0: #一個しかないのでm0が更新されてm1がm0, m2がm1となる
            heappop(HQ) #m0が取り除かれる
            m0 = heappop(HQ)
            while removed[HQ[0]] == 1:
                removed[HQ[0]] -=1
                heappop(HQ)
            m1 = HQ[0] #新しいm1
            heappush(HQ,m0) #m0を戻す
        elif removed[A[left]] == 1: #ちょうど二個の場合にはm0=m1でm1が次に更新
            heappop(HQ) #m0の一個目
            heappop(HQ) #m0の二個目
            while removed[HQ[0]] == 1:
                removed[HQ[0]] -=1
                heappop(HQ)
            m1 = HQ[0] #新しいm1
            removed[A[left]] -= 1 #1個減る
        else:
            removed[A[left]] -= 1 #1個減る

    #print("saigo",left,right,HQ,removed,"M0",m0,"M1",m1,"M",M)
ans = All - cnt
print(ans)
0