結果

問題 No.1435 Mmm......
ユーザー H3PO4H3PO4
提出日時 2022-05-19 09:34:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 564 ms / 2,000 ms
コード長 1,455 bytes
コンパイル時間 318 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 109,696 KB
最終ジャッジ日時 2024-09-17 15:03:42
合計ジャッジ時間 13,084 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq
from collections import Counter

input = sys.stdin.buffer.readline


class CounterWithMin(Counter):
    __slots__ = ["h"]

    def __init__(self, iterable=tuple()):
        super(CounterWithMin, self).__init__(iterable)
        self.h = list(set(iterable))
        heapq.heapify(self.h)

    def add(self, x):
        if x in self:
            self[x] += 1
        else:
            self[x] = 1
            heapq.heappush(self.h, x)

    def remove(self, x):
        if x not in self:
            raise ValueError(f"{x} not in Counter")
        if self[x] == 1:
            del self[x]
        else:
            self[x] -= 1

    def min(self):
        if not super(CounterWithMin, self).__len__():
            raise ValueError
        while self.h and self.h[0] not in self:
            heapq.heappop(self.h)
        return self.h[0]


N = int(input())
A = tuple(map(int, input().split()))

m1 = min(A[:2])
ct_M = CounterWithMin([-A[0], -A[1]])
ct_m2 = CounterWithMin([max(A[:2])])
ans = 1  # (l,r)=(0,1) は必ず条件を満たす
l = 0
for r in range(2, N):
    ar = A[r]
    ct_M.add(-ar)
    if m1 <= ar:
        ct_m2.add(ar)
    else:
        ct_m2.add(m1)
        m1 = ar
    while -ct_M.min() > m1 + ct_m2.min():
        al = A[l]
        if m1 == al:
            m1 = ct_m2.min()
            ct_m2.remove(m1)
        else:
            ct_m2.remove(al)
        ct_M.remove(-al)
        l += 1
    ans += r - l
print(ans)
0